题目链接：
题目分析
题目询问一条路径上的信息时，每次询问有某种特定的文化的点。
每个点的文化就相当于一种颜色，每次询问一条路径上某种颜色的点的信息。
可以使用离线算法， 类似于“郁闷的小 J ” 那道题目。将各种操作和询问按照颜色为第一关键字，时间为第二关键字排序。
那么修改颜色的操作就相当于在原颜色中是删点，在新颜色中是加点。
处理完一种颜色的操作后，要将这个颜色的点都做一次删除操作，这样，对于处理下一种颜色，树就又是空的了。
这种题，思考的时候有点晕，写代码的时候非常愉悦。
代码
#include#include #include #include #include #include #include using namespace std;inline void Read(int &Num){ char c = getchar(); bool Neg = false; while (c < '0' || c > '9') { if (c == '-') Neg = true; c = getchar(); } Num = c - '0'; c = getchar(); while (c >= '0' && c <= '9') { Num = Num * 10 + c - '0'; c = getchar(); } if (Neg) Num = -Num;}inline int gmin(int a, int b) {return a < b ? a : b;}inline int gmax(int a, int b) {return a > b ? a : b;}const int MaxN = 100000 + 5, MaxM = 100000 + 5, INF = 999999999;int n, m, QTop, ATot;int W[MaxN], C[MaxN], WT[MaxN], CT[MaxN], Ans[MaxM], Father[MaxN], T[MaxN], Sum[MaxN], Max[MaxN], Son[MaxN][2];bool isRoot[MaxN], Rev[MaxN];struct Edge{ int v; Edge *Next;} E[MaxN * 2], *P = E, *Point[MaxN];inline void AddEdge(int x, int y){ ++P; P -> v = y; P -> Next = Point[x]; Point[x] = P;}struct ES{ int Type, Col, Pos, Num, x, y, TL, AIdx; /* TypeList: 1 : Change City-Pos to Num 2 : Qsum of the path(x, y) 3 : Qmax of the path(x, y) */} Q[MaxN * 2 + MaxM * 2];inline bool Cmp(ES e1, ES e2){ if (e1.Col != e2.Col) return e1.Col < e2.Col; return e1.TL < e2.TL;}queue Qe; void BFS(){ while (!Qe.empty()) Qe.pop(); Qe.push(1); Father[1] = 0; int x; while (!Qe.empty()) { x = Qe.front(); Qe.pop(); for (Edge *j = Point[x]; j; j = j -> Next) { if (j -> v == Father[x]) continue; Father[j -> v] = x; Qe.push(j -> v); } }}/************************ LCT Start ****************************/inline void Update(int x){ Sum[x] = Sum[Son[x][0]] + Sum[Son[x][1]] + T[x]; Max[x] = gmax(T[x], gmax(Max[Son[x][0]], Max[Son[x][1]]));}inline void Reverse(int x){ Rev[x] = !Rev[x]; swap(Son[x][0], Son[x][1]);}inline void PushDown(int x){ if (!Rev[x]) return; Rev[x] = false; if (Son[x][0]) Reverse(Son[x][0]); if (Son[x][1]) Reverse(Son[x][1]);}inline int GetDir(int x) {return x == Son[Father[x]][0] ? 0 : 1;}void Rotate(int x){ int y = Father[x], f = GetDir(x) ^ 1; PushDown(y); PushDown(x); if (isRoot[y]) { isRoot[y] = false; isRoot[x] = true; } else Son[Father[y]][GetDir(y)] = x; Father[x] = Father[y]; Son[y][f ^ 1] = Son[x][f]; if (Son[x][f]) Father[Son[x][f]] = y; Son[x][f] = y; Father[y] = x; Update(y); Update(x);}void Splay(int x){ int y; while (!isRoot[x]) { y = Father[x]; if (isRoot[y]) { Rotate(x); break; } if (GetDir(x) == GetDir(y)) Rotate(y); else Rotate(x); Rotate(x); }}inline int Access(int x){ int y = 0; while (x != 0) { Splay(x); PushDown(x); if (Son[x][1]) isRoot[Son[x][1]] = true; Son[x][1] = y; if (y) isRoot[y] = false; Update(x); y = x; x = Father[x]; } return y;}inline void Make_Root(int x){ int t = Access(x); Reverse(t);}/************************ LCT End ****************************/int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { Read(W[i]); Read(C[i]); WT[i] = W[i]; CT[i] = C[i]; } int a, b; for (int i = 1; i <= n - 1; ++i) { Read(a); Read(b); AddEdge(a, b); AddEdge(b, a); } char Str[5]; for (int i = 1; i <= n; ++i) { ++QTop; Q[QTop].TL = 0; Q[QTop].Col = CT[i]; Q[QTop].Type = 1; Q[QTop].Pos = i; Q[QTop].Num = WT[i]; } for (int i = 1; i <= m; ++i) { scanf("%s", Str); Read(a); Read(b); if (strcmp(Str, "CC") == 0) { ++QTop; Q[QTop].TL = i; Q[QTop].Col = CT[a]; Q[QTop].Type = 1; Q[QTop].Pos = a; Q[QTop].Num = 0; ++QTop; Q[QTop].TL = i; Q[QTop].Col = b; Q[QTop].Type = 1; Q[QTop].Pos = a; Q[QTop].Num = WT[a]; CT[a] = b; } else if (strcmp(Str, "CW") == 0) { ++QTop; Q[QTop].TL = i; Q[QTop].Col = CT[a]; Q[QTop].Type = 1; Q[QTop].Pos = a; Q[QTop].Num = b; WT[a] = b; } else if (strcmp(Str, "QS") == 0) { ++QTop; Q[QTop].TL = i; Q[QTop].Col = CT[a]; Q[QTop].Type = 2; Q[QTop].x = a; Q[QTop].y = b; Q[QTop].AIdx = ++ATot; } else if (strcmp(Str, "QM") == 0) { ++QTop; Q[QTop].TL = i; Q[QTop].Col = CT[a]; Q[QTop].Type = 3; Q[QTop].x = a; Q[QTop].y = b; Q[QTop].AIdx = ++ATot; } } for (int i = 1; i <= n; ++i) { ++QTop; Q[QTop].TL = INF; Q[QTop].Col = CT[i]; Q[QTop].Type = 1; Q[QTop].Pos = i; Q[QTop].Num = 0; } sort(Q + 1, Q + QTop + 1, Cmp); BFS(); for (int i = 1; i <= n; ++i) { isRoot[i] = true; Rev[i] = false; T[i] = 0; Max[i] = 0; Sum[i] = 0; } int t; for (int i = 1; i <= QTop; ++i) { if (Q[i].Type == 1) { Splay(Q[i].Pos); T[Q[i].Pos] = Q[i].Num; Update(Q[i].Pos); } else { Make_Root(Q[i].x); t = Access(Q[i].y); if (Q[i].Type == 2) Ans[Q[i].AIdx] = Sum[t]; else Ans[Q[i].AIdx] = Max[t]; } } for (int i = 1; i <= ATot; ++i) printf("%d\n", Ans[i]); return 0;}