题目大意
给出一个树，树上每个节点有两个权值，分别是这个节点的宗教评级和这个节点信仰的宗教。多次修改这两个权值，每次询问树上路径上的点的同一个宗教的最大评级和评级和。
思路
不要想太多，每个宗教建立一颗线段树，空间开不下考虑一下动态节点线段树。之后在每个线段树上维护一下树链剖分就行了。 你们想知道c的取值范围么？ [0,10^5]
CODE;struct SegTree *nil;struct SegTree{SegTree *son[2];int _max,sum;SegTree() {_max = sum = 0;son[0] = son[1] = nil;}void Modify(int l,int r,int x,int c) {if(l == r) {_max = sum = c;return ;}int mid = (l + r) >> 1;if(x <= mid) {if(son[0] == nil)son[0] = new SegTree();son[0]->Modify(l,mid,x,c);}else {if(son[1] == nil)son[1] = new SegTree();son[1]->Modify(mid + 1,r,x,c);}_max = max(son[0]->_max,son[1]->_max);sum = son[0]->sum + son[1]->sum;}int GetSum(int l,int r,int x,int y) {if(this == nil) return 0;if(l == x && y == r) return sum;int mid = (l + r) >> 1;if(y <= mid) return son[0]->GetSum(l,mid,x,y);if(x > mid)return son[1]->GetSum(mid + 1,r,x,y);int left = son[0]->GetSum(l,mid,x,mid);int right = son[1]->GetSum(mid + 1,r,mid + 1,y);return left + right;}int GetMax(int l,int r,int x,int y) {if(this == nil) return 0;if(l == x && y == r) return _max;int mid = (l + r) >> 1;if(y <= mid) return son[0]->GetMax(l,mid,x,y);if(x > mid)return son[1]->GetMax(mid + 1,r,x,y);int left = son[0]->GetMax(l,mid,x,mid);int right = son[1]->GetMax(mid + 1,r,mid + 1,y);return max(left,right);}}none,*root[MAX];int points,asks;int head[MAX],total;int _next[MAX << 1],aim[MAX << 1];inline void Add(int x,int y){_next[++total] = head[x];aim[total] = y;head[x] = total;}int p[MAX],belief[MAX];int size[MAX],son[MAX],father[MAX],deep[MAX];int top[MAX],pos[MAX],cnt;void PreDFS(int x,int last){deep[x] = deep[last] + 1;father[x] = last;size[x] = 1;int max_size = 0;for(int i = head[x]; i; i = _next[i]) {if(aim[i] == last) continue;PreDFS(aim[i],x);size[x] += size[aim[i]];if(size[aim[i]] > max_size)max_size = size[aim[i]],son[x] = aim[i];}}void DFS(int x,int last,int _top){pos[x] = ++cnt;top[x] = _top;if(son[x]) DFS(son[x],x,_top);for(int i = head[x]; i; i = _next[i]) {if(aim[i] == last || aim[i] == son[x]) continue;DFS(aim[i],x,aim[i]);}}inline int GetSum(int x,int y,int p){int re = 0;while(top[x] != top[y]) {if(deep[top[x]] < deep[top[y]]) swap(x,y);re += root[p]->GetSum(1,points,pos[top[x]],pos[x]);x = father[top[x]];}if(deep[x] < deep[y]) swap(x,y);re += root[p]->GetSum(1,points,pos[y],pos[x]);return re;}inline int GetMax(int x,int y,int p){int re = 0;while(top[x] != top[y]) {if(deep[top[x]] < deep[top[y]]) swap(x,y);re = max(re,root[p]->GetMax(1,points,pos[top[x]],pos[x]));x = father[top[x]];}if(deep[x] < deep[y]) swap(x,y);re = max(re,root[p]->GetMax(1,points,pos[y],pos[x]));return re;}char s[10];int main(){nil = &none;cin >> points >> asks;for(int i = 0; i < MAX; ++i)root[i] = new SegTree();for(int i = 1; i <= points; ++i)scanf(“%d%d”,&p[i],&belief[i]);for(int x,y,i = 1; i < points; ++i) {scanf(“%d%d”,&x,&y);Add(x,y),Add(y,x);}PreDFS(1,0);DFS(1,0,1);for(int i = 1; i <= points; ++i)root[belief[i]]->Modify(1,points,pos[i],p[i]);for(int x,y,i = 1; i <= asks; ++i) {scanf(“%s%d%d”,s,&x,&y);if(s[0] == ‘C’ && s[1] == ‘C’) {root[belief[x]]->Modify(1,points,pos[x],0);root[belief[x] = y]->Modify(1,points,pos[x],p[x]);}else if(s[0] == ‘C’ && s[1] == ‘W’)root[belief[x]]->Modify(1,points,pos[x],p[x] = y);else if(s[0] == ‘Q’ && s[1] == ‘S’)printf(“%d\n”,GetSum(x,y,belief[x]));elseprintf(“%d\n”,GetMax(x,y,belief[x]));}return 0;}
，成功是什么?就是走过了所有通向失败的路.只剩下一条路.那就是成功的路.
