写完题去网上逛一圈发现全都是离线LCA，Orz。
大致题意是一颗树上边有边权和颜色，每次询问会先把颜色为x的边的边权变为y，再询问u到v的边权和。注意，每次询问的修改只针对当前询问。
由于题目是树上距离，所以树剖大致是可以做的。
树剖完后将每条边的边权转点权，赋给深度较高的节点。
每次查询，我们只要知道两点的权值和sum1，颜色为x的边的权值和sum2以及颜色为x的边的个数num，则答案为$sum1-sum2+num*y$。
所以就建权值线段树，以颜色为权值，同时维护颜色个数以及这种颜色的权值和。
就是普普通通的树剖主席树啦QAQ
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxm = 1e6 + 10;
4 const int maxn = 3e5+10;
5 typedef long long ll;
6 struct node {
7 int s, e, c, w, next;
8 }edge[maxn];
9 int head[maxn], len;
10 int n, q;
11 void init() {
12 memset(head, -1, sizeof(head));
13 len = 0;
14 }
15 void add(int s, int e, int c, int w) {
16 edge[len].s = s;
17 edge[len].e = e;
18 edge[len].w = w;
19 edge[len].c = c;
20 edge[len].next = head[s];
21 head[s] = len++;
22 }
23 int son[maxn], top[maxn], tid[maxn], fat[maxn], siz[maxn], dep[maxn], rak[maxn];
24 int dfx;
25 void dfs1(int x, int fa, int d) {
26 siz[x] = 1, son[x] = -1, fat[x] = fa, dep[x] = d;
27 for (int i = head[x]; i != -1; i = edge[i].next) {
28 int y = edge[i].e;
29 if (y == fa)
30 continue;
31 dfs1(y, x, d + 1);
32 siz[x] += siz[y];
33 if (son[x] == -1 || siz[y] > siz[son[x]])
34 son[x] = y;
35 }
36 }
37 void dfs2(int x, int c) {
38 top[x] = c; tid[x] = ++dfx; rak[dfx] = x;
39 if (son[x] == -1)
40 return;
41 dfs2(son[x], c);
42 for (int i = head[x]; i != -1; i = edge[i].next) {
43 int y = edge[i].e;
44 if (y == fat[x] || y == son[x])
45 continue;
46 dfs2(y, y);
47 }
48 }
49 int cnt, root[maxn], ls[maxn * 40], rs[maxn * 40], num[maxn * 40], val[maxn * 40];
50 struct C {
51 int color, dis;
52 }a[maxn];
53 void build(C k, int l, int r, int& i) {
54 num[++cnt] = num[i] + 1, val[cnt] = val[i] + k.dis, ls[cnt] = ls[i], rs[cnt] = rs[i];
55 i = cnt;
56 if (l == r)
57 return;
58 int mid = l + r >> 1;
59 if (k.color <= mid)
60 build(k, l, mid, ls[i]);
61 else
62 build(k, mid + 1, r, rs[i]);
63 }
64 C query(int u, int v, int k, int l, int r) {
65 if (l == r) {
66 return { num[v] - num[u],val[v] - val[u] };
67 }
68
69 int mid = l + r >> 1;
70 if (k <= mid)
71 return query(ls[u], ls[v], k, l, mid);
72 else
73 return query(rs[u], rs[v], k, mid + 1, r);
74 }
75 int solve(int cr, int dis, int x, int y) {
76 C ans = { 0,0 };
77 int sum = 0;
78 while (top[x] != top[y]) {
79 if (dep[top[x]] < dep[top[y]])
80 swap(x, y);
81 C t = query(root[tid[top[x]] - 1], root[tid[x]], cr, 1, n);
82 sum += val[root[tid[x]]] - val[root[tid[top[x]] - 1]];
83 ans.color += t.color, ans.dis += t.dis;
84 x = fat[top[x]];
85 }
86
87 if (x != y) {
88 if (dep[x] < dep[y])
89 swap(x, y);
90 C t = query(root[tid[son[y]] - 1], root[tid[x]], cr, 1, n);
91 sum += val[root[tid[x]]] - val[root[tid[son[y]] - 1]];
92 ans.color += t.color, ans.dis += t.dis;
93 }
94 return sum - ans.dis + ans.color * dis;
95 }
96 int main() {
97 scanf("%d%d", &n, &q);
98 init();
99 for (int i = 1, x, y, c, d; i < n; i++) {
100 scanf("%d%d%d%d", &x, &y, &c, &d);
101 add(x, y, c, d);
102 add(y, x, c, d);
103 }
104 dfs1(1, 0, 1);
105 dfs2(1, 1);
106 for (int i = 0; i < len; i += 2) {
107 int x = edge[i].e;
108 int y = edge[i].s;
109 if (dep[x] < dep[y])
110 swap(x, y);
111 a[tid[x]] = { edge[i].c, edge[i].w };
112 }
113 for (int i = 2; i <= dfx; i++) {
114 root[i] = root[i - 1];
115 build(a[i], 1, n, root[i]);
116 }
117 while (q--) {
118 int x, y, u, v;
119 scanf("%d%d%d%d", &x, &y, &u, &v);
120 printf("%d\n", solve(x, y, u, v));
121 }
122 }