总算把几个月前WA的题A了。
看到树上路径的操作，就能想到树剖。
不过要是给每一个宗教都开一个线段树的话肯定会MLE，所以我们动态开点就行啦。
然后debug了一小会儿，全是因为一些zz小错误，什么连接表遍历出边写错了，查询最大值从查询区间和复制下来却没改完……对了，这两个最好分开写，虽然代码可能会长一点，但是每一个函数里面结构还是特别清晰的。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e5 + 5; 21 const int max_tre = 1e7 + 5; 22 inline ll read() 23 { 24 ll ans = 0; 25 char ch = getchar(), last = ' '; 26 while(!isdigit(ch)) {last = ch; ch = getchar();} 27 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 28 if(last == '-') ans = -ans; 29 return ans; 30 } 31 inline void write(ll x) 32 { 33 if(x < 0) x = -x, putchar('-'); 34 if(x >= 10) write(x / 10); 35 putchar(x % 10 + '0'); 36 } 37 38 int n, q, w[maxn], c[maxn]; 39 40 struct Edge 41 { 42 int nxt, to; 43 }e[maxn << 1]; 44 int head[maxn], ecnt = 0; 45 void addEdge(int x, int y) 46 { 47 e[++ecnt] = (Edge){head[x], y}; 48 head[x] = ecnt; 49 } 50 51 int dep[maxn], fa[maxn], siz[maxn], son[maxn]; 52 void dfs1(int now, int f) 53 { 54 siz[now] = 1; 55 for(int i = head[now]; i; i = e[i].nxt) 56 { 57 if(e[i].to == f) continue; 58 dep[e[i].to] = dep[now] + 1; 59 fa[e[i].to] = now; 60 dfs1(e[i].to, now); 61 siz[now] += siz[e[i].to]; 62 if(!son[now] || siz[son[now]] < siz[e[i].to]) son[now] = e[i].to; 63 } 64 } 65 int top[maxn], dfsx[maxn], cnt = 0; 66 void dfs2(int now, int f) 67 { 68 dfsx[now] = ++cnt; 69 if(son[now]) 70 { 71 top[son[now]] = top[now]; 72 dfs2(son[now], now); 73 } 74 for(int i = head[now]; i; i = e[i].nxt) 75 { 76 if(e[i].to == son[now] || e[i].to == f) continue; 77 top[e[i].to] = e[i].to; 78 dfs2(e[i].to, now); 79 } 80 } 81 82 int ctr = 0, root[maxn], ls[max_tre], rs[max_tre], Max[max_tre], sum[max_tre]; 83 void update(int &now, int l, int r, int idx, int d) 84 { 85 if(!now) now = ++ctr; 86 if(l == r) {Max[now] = sum[now] = d; return;} 87 int mid = (l + r) >> 1; 88 if(idx <= mid) update(ls[now], l, mid, idx, d); 89 else update(rs[now], mid + 1, r, idx, d); 90 sum[now] = sum[ls[now]] + sum[rs[now]]; 91 Max[now] = max(Max[ls[now]], Max[rs[now]]); 92 } 93 int query_Sum(int now, int l, int r, int L, int R) 94 { 95 if(!now) return 0; 96 if(l == L && r == R) return sum[now]; 97 int mid = (l + r) >> 1; 98 if(R <= mid) return query_Sum(ls[now], l, mid, L, R); 99 else if(L > mid) return query_Sum(rs[now], mid + 1, r, L, R);100 else return query_Sum(ls[now], l, mid, L, mid) + query_Sum(rs[now], mid + 1, r, mid + 1, R);101 }102 int query_Max(int now, int l, int r, int L, int R)103 {104 if(!now) return 0;105 if(l == L && r == R) return Max[now];106 int mid = (l + r) >> 1;107 if(R <= mid) return query_Max(ls[now], l, mid, L, R);108 else if(L > mid) return query_Max(rs[now], mid + 1, r, L, R);109 else return max(query_Max(ls[now], l, mid, L, mid), query_Max(rs[now], mid + 1, r, mid + 1, R));110 }111 int queryS_path(int x, int y)112 {113 int col = c[x], ret = 0;114 while(top[x] != top[y])115 {116 if(dep[top[x]] < dep[top[y]]) swap(x, y);117 ret += query_Sum(root[col], 1, cnt, dfsx[top[x]], dfsx[x]);118 x = fa[top[x]];119 }120 if(dfsx[x] < dfsx[y]) swap(x, y);121 ret += query_Sum(root[col], 1, cnt, dfsx[y], dfsx[x]);122 return ret;123 }124 int queryM_path(int x, int y)125 {126 int col = c[x], ret = 0;127 while(top[x] != top[y])128 {129 if(dep[top[x]] < dep[top[y]]) swap(x, y);130 ret = max(ret, query_Max(root[col], 1, cnt, dfsx[top[x]], dfsx[x]));131 x = fa[top[x]];132 }133 if(dfsx[x] < dfsx[y]) swap(x, y);134 ret = max(ret, query_Max(root[col], 1, cnt, dfsx[y], dfsx[x]));135 return ret;136 }137 138 char s[2];139 140 int main()141 {142 n = read(); q = read();143 for(int i = 1; i <= n; ++i) w[i] = read(), c[i] = read();144 for(int i = 1; i < n; ++i)145 {146 int x = read(), y = read();147 addEdge(x, y); addEdge(y, x);148 }149 dfs1(1, 0); top[1] = 1; dfs2(1, 0);150 for(int i = 1; i <= n; ++i) update(root[c[i]], 1, cnt, dfsx[i], w[i]);151 for(int i = 1; i <= q; ++i)152 {153 scanf("%s", s); int x = read(), y = read();154 if(s[1] == 'C')155 {156 update(root[c[x]], 1, cnt, dfsx[x], 0);157 c[x] = y;158 update(root[c[x]], 1, cnt, dfsx[x], w[x]);159 }160 else if(s[1] == 'W')161 {162 w[x] = y;163 update(root[c[x]], 1, cnt, dfsx[x], w[x]);164 }165 else if(s[1] == 'S') write(queryS_path(x, y)), enter;166 else write(queryM_path(x, y)), enter;167 }168 return 0;169 }