人生第一道树链剖分的题目，其实树链剖分并不是特别难。
思想就是把树剖成一些轻链和重链，轻链比较少可以直接修改，重链比较长，用线段树去维护。
貌似大家都是从上学的。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int maxn = 10000 + 10; 8 9 int n; 10 int tot; 11 vector G[maxn]; 12 int u[maxn], v[maxn], d[maxn]; 13 14 int fa[maxn]; 15 int top[maxn]; 16 int id[maxn]; 17 int L[maxn]; 18 int son[maxn]; 19 int sz[maxn]; 20 21 void dfs(int u) 22 { 23 sz[u] = 1; son[u] = 0; 24 for(int i = 0; i < G[u].size(); i++) 25 { 26 int v = G[u][i]; 27 if(v == fa[u]) continue; 28 fa[v] = u; 29 L[v] = L[u] + 1; 30 dfs(v); 31 sz[u] += sz[v]; 32 if(sz[v] > sz[son[u]]) son[u] = v; 33 } 34 } 35 36 void dfs2(int u, int tp) 37 { 38 id[u] = ++tot; 39 top[u] = tp; 40 if(son[u]) dfs2(son[u], tp); 41 for(int i = 0; i < G[u].size(); i++) 42 { 43 int v = G[u][i]; 44 if(v == fa[u] || v == son[u]) continue; 45 dfs2(v, v); 46 } 47 } 48 49 int maxv[maxn << 2]; 50 51 void update(int o, int L, int R, int p, int val) 52 { 53 if(p < L || p > R) return ; 54 if(L == R) { maxv[o] = val; return ; } 55 int M = (L + R) / 2; 56 update(o<<1, L, M, p, val); 57 update(o<<1|1, M+1, R, p, val); 58 maxv[o] = max(maxv[o<<1], maxv[o<<1|1]); 59 } 60 61 int query(int o, int L, int R, int qL, int qR) 62 { 63 if(qR < L || qL > R) return 0; 64 if(qL <= L && R <= qR) return maxv[o]; 65 int M = (L + R) / 2; 66 return max(query(o<<1, L, M, qL, qR), query(o<<1|1, M+1, R, qL, qR)); 67 } 68 69 int QUERY(int u, int v) 70 { 71 int ans = 0; 72 int t1 = top[u], t2 = top[v]; 73 while(t1 != t2) 74 { 75 if(L[t1] < L[t2]) { swap(u, v); swap(t1, t2); } 76 ans = max(ans, query(1, 1, tot, id[t1], id[u])); 77 u = fa[t1]; t1 = top[u]; 78 } 79 if(u == v) return ans; 80 if(L[u] < L[v]) swap(u, v); 81 ans = max(ans, query(1, 1, tot, id[son[v]], id[u])); 82 return ans; 83 } 84 85 int main() 86 { 87 int T; scanf("%d", &T); 88 while(T--) 89 { 90 scanf("%d", &n); 91 for(int i = 1; i <= n; i++) G[i].clear(); 92 fa[1] = L[1] = 0; 93 for(int i = 1; i < n; i++) 94 { 95 scanf("%d%d%d", u + i, v + i, d + i); 96 G[u[i]].push_back(v[i]); 97 G[v[i]].push_back(u[i]); 98 } 99 100 dfs(1);101 tot = 0;102 dfs2(1, 1);103 104 memset(maxv, 0, sizeof(maxv));105 for(int i = 1; i < n; i++)106 {107 if(L[u[i]] < L[v[i]]) swap(u[i], v[i]);108 update(1, 1, tot, id[u[i]], d[i]);109 }110 111 char op[30];112 while(scanf("%s", op) && op[0] != 'D')113 {114 int x, y; scanf("%d%d", &x, &y);115 if(op[0] == 'Q')116 {117 printf("%d\n", QUERY(x, y));118 }119 else120 {121 update(1, 1, tot, id[u[x]], y);122 }123 }124 }125 126 return 0;127 }