# 树链剖分专题

*注意一下poj好像是提交的代码包含/**/这样的注释会出问题

A、HDU 3966

‘D’：将C1到C2路径上的点减少K；

‘Q’：问你C点上的权；

`#pragma comment(linker, "/STACK:1024000000,1024000000") `

```  1 /*
2  * Problem:
3  * Author:  SHJWUDP
4  * Created Time:  2015/6/11 星期四 12:10:10
5  * File Name: 233.cpp
6  * State:
7  * Memo:
8  */
10 #include <iostream>
11 #include <cstdio>
12 #include <cstring>
13 #include <algorithm>
14 using namespace std;
15
16 typedef long long int64;
17
18 const int MaxA=5e4+7;
19
20 struct Edge {
21     int v, nt;
22     Edge() {}
23     Edge(int v, int nt):v(v), nt(nt) {}
24 } edges[MaxA<<1];
25
27
28 struct Fenwick {
29     int n;
30     int c[MaxA];
31
32     void init(int n) {
33         this->n=n;
34         memset(c, 0, sizeof(c[0])*(n+3));
35     }
36
37     int lowbit(int x) {
38         return x&(-x);
39     }
40
41     void update(int x, int d) {
42         while(x>0) {
43             c[x]+=d;
44             x-=lowbit(x);
45         }
46     }
47
48     int query(int x) {
49         int res=0;
50         while(x<=n) {
51             res+=c[x];
52             x+=lowbit(x);
53         }
54         return res;
55     }
56 } fw;
57
58 int N, M, P;
59 int oval[MaxA], val[MaxA];
60
61 void init() {
63     edgeNum=0;
64 }
65 void addEdge(int u, int v) {
68 }
69 namespace LCT {
70     int fa[MaxA];
71     int dep[MaxA];
72     int siz[MaxA];
73     int son[MaxA];
74     int top[MaxA];
75     int w[MaxA];
76     int id;
77
78     int dfs1(int u, int d) {
79         dep[u]=d; siz[u]=1; son[u]=-1;
80         for(int i=head[u]; ~i; i=edges[i].nt) {
81             Edge& e=edges[i];
82             if(e.v==fa[u]) continue;
83             fa[e.v]=u;
84             siz[u]+=dfs1(e.v, d+1);
85             if(son[u]==-1 || siz[son[u]]<siz[e.v]) son[u]=e.v;
86         }
87         return siz[u];
88     }
89
90     void dfs2(int u, int tp) {
91         w[u]=++id; top[u]=tp;
92         if(~son[u]) dfs2(son[u], tp);
93         for(int i=head[u]; ~i; i=edges[i].nt) {
94             Edge& e=edges[i];
95             if(e.v==fa[u] || e.v==son[u]) continue;
96             dfs2(e.v, e.v);
97         }
98     }
99
100     void init() {
101         int root=1;
102         id=0;
103         fa[root]=-1;
104         dfs1(root, 0);
105         dfs2(root, root);
106         fw.init(N);
107         for(int i=1; i<=N; i++) {
108             fw.update(w[i]-1, -oval[i]);
109             fw.update(w[i], oval[i]);
110         }
111     }
112
113     void update(int u, int v, int d) {
114         int f1=top[u], f2=top[v];
115         while(f1!=f2) {
116             if(dep[f1]<dep[f2]) { swap(f1, f2); swap(u, v); }
117             fw.update(w[f1]-1, -d); fw.update(w[u], d);
118             u=fa[f1]; f1=top[u];
119         }
120         if(dep[u]>dep[v]) swap(u, v);
121         fw.update(w[u]-1, -d);    fw.update(w[v], d);
122     }
123
124     int query(int x) {
125         return fw.query(w[x]);
126     }
127 }
128 int main() {
129 #ifndef ONLINE_JUDGE
130     freopen("in", "r", stdin);
131     //freopen("out", "w", stdout);
132 #endif
133     while(~scanf("%d%d%d", &N, &M, &P)) {
134         for(int i=1; i<=N; i++) {
135             scanf("%d", &oval[i]);
136         }
137         init();
138         for(int i=0; i<M; i++) {
139             int a, b;
140             scanf("%d%d", &a, &b);
143         }
144         LCT::init();
145         while(P--) {
146             char op[2];
147             scanf("%s", op);
148             if(op[0]==‘Q‘) {
149                 int x;
150                 scanf("%d", &x);
151                 printf("%d\n", LCT::query(x));
152             } else {
153                 int a, b, c;
154                 scanf("%d%d%d", &a, &b, &c);
155                 if(op[0]==‘D‘) c=-c;
156                 LCT::update(a, b, c);
157             }
158         }
159     }
160     return 0;
161 }```

‘Q a b’：询问节点a到节点b（包括a和b）路径上的颜色段数量；

```  1 /**************************************************************
2     Problem: 2243
3     User: shjwudp
4     Language: C++
5     Result: Accepted
6     Time:4324 ms
7     Memory:17388 kb
8 ****************************************************************/
9
10 /*
11  * Problem:
12  * Author:  SHJWUDP
13  * Created Time:  2015/6/11 星期四 19:27:57
14  * File Name: 233.cpp
15  * State:
16  * Memo:
17  */
18 #include <iostream>
19 #include <cstdio>
20 #include <cstring>
21 #include <algorithm>
22
23 using namespace std;
24
25 const int MaxA=1e5+7;
26
27 struct Edge {
28     int v, nt;
29     Edge(){}
30     Edge(int v, int nt):v(v), nt(nt){}
31 } edges[MaxA<<1];
32
34
35 struct SegmentTree {
36     struct Node {
37         int l, r;
38         int cnt;
39         int mark;
40     } c[MaxA<<2];
41     int n;
42     int *val;
43     int L, R, v;
44 #define lson l, m, rt<<1
45 #define rson m+1, r, rt<<1|1
46 #define RUSH Node& u=c[rt]; Node& ls=c[rt<<1]; Node& rs=c[rt<<1|1];
47
48     void pushUp(int rt) {
49         RUSH
50         u.cnt=ls.cnt+rs.cnt-(ls.r==rs.l?1:0);
51         u.l=ls.l;
52         u.r=rs.r;
53     }
54
55     void pushDown(int rt) {
56         RUSH
57         if(~u.mark) {
58             ls.mark=rs.mark=ls.l=ls.r=rs.l=rs.r=u.mark;
59             ls.cnt=rs.cnt=1;
60             u.mark=-1;
61         }
62     }
63
64     void doBuild(int l, int r, int rt) {
65         c[rt].mark=-1;
66         if(l==r) {
67             c[rt].l=c[rt].r=val[l];
68             c[rt].cnt=1;
69         } else {
70             int m=(l+r)>>1;
71             doBuild(lson);
72             doBuild(rson);
73             pushUp(rt);
74         }
75     }
76
77     void build(int n, int *val) {
78         this->n=n; this->val=val;
79         doBuild(1, n, 1);
80     }
81
82     void doColor(int l, int r, int rt) {
83         if(L<=l && r<=R) {
84             c[rt].l=c[rt].r=c[rt].mark=v;
85             c[rt].cnt=1;
86         } else {
87             pushDown(rt);
88             int m=(l+r)>>1;
89             if(L<=m) doColor(lson);
90             if(m<R) doColor(rson);
91             pushUp(rt);
92         }
93     }
94
95     void color(int L, int R, int v) {
96         this->L=L; this->R=R; this->v=v;
97         doColor(1, n, 1);
98     }
99
100     int doQuery(int l, int r, int rt) {
101         RUSH
102         if(L<=l && r<=R) {
103             return u.cnt;
104         } else {
105             pushDown(rt);
106             int m=(l+r)>>1;
107             int res=0;
108             if(L<=m) res+=doQuery(lson);
109             if(m<R) res+=doQuery(rson)-(res&&ls.r==rs.l?1:0);
110             return res;
111         }
112     }
113
114     int query(int L, int R) {
115         this->L=L; this->R=R;
116         return doQuery(1, n, 1);
117     }
118
119     int qcolor(int p) {
120         int l=1, r=n, rt=1;
121         while(l<r) {
122             pushDown(rt);
123             int m=(l+r)>>1;
124             if(p<=m) r=m, rt=rt<<1;
125             else l=m+1, rt=rt<<1|1;
126         }
127         return c[rt].l;
128     }
129
130 #undef lson
131 #undef rson
132 #undef RUSH
133 } st;
134
135 int N, M;
136 int oval[MaxA], val[MaxA];  ///oval:原树上结点编号到值的映射
137                             ///val:树剖后生成的线性表上编号到值的映射
138 void init() {
139     edgeNum=0;
141 }
142 void addEdge(int u, int v) {
145 }
146 namespace LCT {
147     int fa[MaxA];
148     int siz[MaxA];
149     int son[MaxA];
150     int dep[MaxA];
151     int top[MaxA];
152     int w[MaxA];
153     int id;
154
155     int dfs1(int u, int d) {
156         siz[u]=1; dep[u]=d; son[u]=-1;
157         for(int i=head[u]; ~i; i=edges[i].nt) {
158             Edge& e=edges[i];
159             if(e.v==fa[u]) continue;
160             fa[e.v]=u;
161             siz[u]+=dfs1(e.v, d+1);
162             if(son[u]==-1 || siz[son[u]]<siz[e.v]) son[u]=e.v;
163         }
164         return siz[u];
165     }
166
167     void dfs2(int u, int tp) {
168         w[u]=++id; top[u]=tp;
169         if(~son[u]) dfs2(son[u], tp);
170         for(int i=head[u]; ~i; i=edges[i].nt) {
171             Edge& e=edges[i];
172             if(e.v==fa[u] || e.v==son[u]) continue;
173             dfs2(e.v, e.v);
174         }
175     }
176
177     void init() {
178         int root=1;
179         id=0;
180         fa[root]=-1;
181         dfs1(root, 0);
182         dfs2(root, root);
183         for(int i=1; i<=N; i++) {
184             val[w[i]]=oval[i];
185         }
186         st.build(N, val);
187     }
188
189     int find(int u, int v) {
190         int res=0;
191         int f1=top[u], f2=top[v];
192         while(f1!=f2) {
193             if(dep[f1]<dep[f2]) { swap(f1, f2); swap(u, v); }
194             res+=st.query(w[f1], w[u])
195                +(fa[f1]!=-1&&st.qcolor(w[f1])==st.qcolor(w[fa[f1]])?-1:0);
196             u=fa[f1]; f1=top[u];
197         }
198         if(dep[u]>dep[v]) swap(u, v);
199         return res+st.query(w[u], w[v]);
200     }
201
202     void update(int u, int v, int op) {
203         int f1=top[u], f2=top[v];
204         while(f1!=f2) {
205             if(dep[f1]<dep[f2]) { swap(f1, f2); swap(u, v); }
206             st.color(w[f1], w[u], op);
207             u=fa[f1]; f1=top[u];
208         }
209         if(dep[u]>dep[v]) swap(u, v);
210         st.color(w[u], w[v], op);
211     }
212 }
213 int main() {
214 #ifndef ONLINE_JUDGE
215     freopen("in", "r", stdin);
216     //freopen("out", "w", stdout);
217 #endif
218     while(~scanf("%d%d", &N, &M)) {
219         for(int i=1; i<=N; i++) {
220             scanf("%d", &oval[i]);
221         }
222         init();
223         for(int i=1; i<N; i++) {
224             int a, b;
225             scanf("%d%d", &a, &b);
228         }
229         LCT::init();
230         while(M--) {
231             char op[2];
232             scanf("%s", op);
233             if(op[0]==‘C‘) {
234                 int a, b, c;
235                 scanf("%d%d%d", &a, &b, &c);
236                 LCT::update(a, b, c);
237             } else {
238                 int a, b;
239                 scanf("%d%d", &a, &b);
240                 printf("%d\n", LCT::find(a, b));
241             }
242         }
243     }
244     return 0;
245 }```

C、POJ 2763

‘1 i w’：将第i条边的边权值变为w；

```  1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5
6 using namespace std;
7
8 const int MaxA=1e5+7;
9
10 struct Edge {
11     int v, nt;
12     int w;
13     Edge(){}
14     Edge(int v, int nt, int w):v(v), nt(nt), w(w) {}
15 } edges[MaxA<<1];
16
18
19 struct Fenwick {
20     int n;
21     int c[MaxA];
22
23     void init(int n) {
24         this->n=n;
25         memset(c, 0, sizeof(c[0])*(n+3));
26     }
27
28     int lowbit(int x) {
29         return x&-x;
30     }
31
32     void update(int x, int d) {
33         while(x<=n) {
34             c[x]+=d;
35             x+=lowbit(x);
36         }
37     }
38
39     int query(int x) {
40         int res=0;
41         while(x>0) {
42             res+=c[x];
43             x-=lowbit(x);
44         }
45         return res;
46     }
47
48     void change(int x, int d) {
49         int tmp=query(x)-query(x-1);
50         update(x, d-tmp);
51     }
52 } fw;
53
54 int N, Q, S;
55 int oval[MaxA];
56 void init() {
58     edgeNum=0;
59 }
60 void addEdge(int u, int v, int w) {
63 }
64 namespace LCT {
65     int fa[MaxA];
66     int siz[MaxA];
67     int son[MaxA];
68     int dep[MaxA];
69     int top[MaxA];
70     int w[MaxA];
71     int e2p[MaxA];    ///边到点的映射
72     int id;
73
74     int dfs1(int u, int d) {
75         siz[u]=1; dep[u]=d; son[u]=-1;
76         for(int i=head[u]; ~i; i=edges[i].nt) {
77             Edge& e=edges[i];
78             if(e.v==fa[u]) continue;
79             e2p[(i>>1)+1]=e.v;    ///边的编号映射到点
80             fa[e.v]=u; oval[e.v]=e.w;    ///以点代边，根节点不代表任何边
81             siz[u]+=dfs1(e.v, d+1);
82             if(son[u]==-1 || siz[son[u]]<siz[e.v]) son[u]=e.v;
83         }
84         return siz[u];
85     }
86
87     void dfs2(int u, int tp) {
88         w[u]=++id; top[u]=tp;
89         if(~son[u]) dfs2(son[u], tp);
90         for(int i=head[u]; ~i; i=edges[i].nt) {
91             Edge& e=edges[i];
92             if(e.v==fa[u] || e.v==son[u]) continue;
93             dfs2(e.v, e.v);
94         }
95     }
96
97     void init() {
98         int root=(N+1)>>1;
99         id=0;
100         fa[root]=-1; oval[root]=0;///以点代边，根节点不代表任何边，因此权为0
101         dfs1(root, 0);
102         dfs2(root, root);
103         fw.init(N);
104         for(int i=1; i<=N; i++) {
105             fw.update(w[i], oval[i]);
106         }
107     }
108
109     int query(int u, int v) {
110         int res=0;
111         int f1=top[u], f2=top[v];
112         while(f1!=f2) {
113             if(dep[f1]<dep[f2]) { swap(f1, f2); swap(u, v); }
114             res+=fw.query(w[u])-fw.query(w[f1]-1);
115             u=fa[f1]; f1=top[u];
116         }
117         if(dep[u]>dep[v]) swap(u, v);
118         return res+fw.query(w[v])-fw.query(w[u]);
119     }
120
121     void update(int x, int d) {
122         fw.change(w[e2p[x]], d);
123     }
124 }
125 int main() {
126 #ifndef ONLINE_JUDGE
127     freopen("in", "r", stdin);
128     //freopen("out", "w", stdout);
129 #endif
130     while(~scanf("%d%d%d", &N, &Q, &S)) {
131         init();
132         for(int i=1; i<N; i++) {
133             int a, b, c;
134             scanf("%d%d%d", &a, &b, &c);
137         }
138         LCT::init();
139         while(Q--) {
140             int op;
141             scanf("%d", &op);
142             if(op==0) {
143                 int x;
144                 scanf("%d", &x);
145                 printf("%d\n", LCT::query(S, x));
146                 S=x;
147             } else {
148                 int a, b;
149                 scanf("%d%d", &a, &b);
150                 LCT::update(a, b);
151             }
152         }
153     }
154     return 0;
155 }```

D、POJ 3237

‘NEGATE a b’：将把节点a到节点b路径上所有边的权值取负；

‘QUERY a b’：询问节点a到节点b路径上的最大边权值；

‘DONE’：操作结束

```  1 /*
2  * Problem:
3  * Author:  SHJWUDP
4  * Created Time:  2015/6/11 星期四 15:57:34
5  * File Name: 233.cpp
6  * State:
7  * Memo:
8  */
9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13
14 using namespace std;
15
16 const int INF=0x7f7f7f7f;
17
18 const int MaxA=1e4+7;
19
20 struct Edge {
21     int v, nt;
22     int w;
23     Edge() {}
24     Edge(int v, int nt, int w):v(v), nt(nt), w(w){}
25 } edges[MaxA<<1];
26
28
29 struct SegmentTree {
30     int n;
31     struct Node {
32         int mx, mi;
33         int mark;
34     } c[MaxA<<2];
35     int *val;
36     int p, v;
37     int L, R;
38 #define lson l, m, rt<<1
39 #define rson m+1, r, rt<<1|1
40 #define RUSH Node& u=c[rt]; Node& ls=c[rt<<1]; Node& rs=c[rt<<1|1];
41
42     void pushUp(int rt) {
43         RUSH
44         u.mx=max(ls.mx, rs.mx);
45         u.mi=min(ls.mi, rs.mi);
46     }
47
48     void pushDown(int rt) {
49         RUSH
50         if(u.mark) {
51             ls.mx=-ls.mx; ls.mi=-ls.mi; swap(ls.mx, ls.mi);
52             ls.mark^=1;
53             rs.mx=-rs.mx; rs.mi=-rs.mi; swap(rs.mx, rs.mi);
54             rs.mark^=1;
55             u.mark=0;
56         }
57     }
58
59     void doBuild(int l, int r, int rt) {
60         c[rt].mark=0;
61         if(l==r) {
62             c[rt].mx=c[rt].mi=val[l];
63         } else {
64             int m=(l+r)>>1;
65             doBuild(lson);
66             doBuild(rson);
67             pushUp(rt);
68         }
69     }
70
71     void build(int n, int *val) {
72         this->n=n; this->val=val;
73         doBuild(1, n, 1);
74     }
75
76     void doChange(int l, int r, int rt) {
77         if(l==r) {
78             c[rt].mx=c[rt].mi=v;
79         } else {
80             pushDown(rt);
81             int m=(l+r)>>1;
82             if(p<=m) doChange(lson);
83             else doChange(rson);
84             pushUp(rt);
85         }
86     }
87
88     void change(int p, int v) {
89         this->p=p; this->v=v;
90         doChange(1, n, 1);
91     }
92
93
94     void doNegate(int l, int r, int rt) {
95         if(L<=l && r<=R) {
96             c[rt].mx=-c[rt].mx; c[rt].mi=-c[rt].mi;
97             swap(c[rt].mx, c[rt].mi);
98             c[rt].mark^=1;
99         } else {
100             pushDown(rt);
101             int m=(l+r)>>1;
102             if(L<=m) doNegate(lson);
103             if(m<R) doNegate(rson);
104             pushUp(rt);
105         }
106     }
107
108     void negate(int L, int R) {
109         this->L=L; this->R=R;
110         doNegate(1, n, 1);
111     }
112
113
114     int doQuery(int l, int r, int rt) {
115         if(L<=l && r<=R) {
116             return c[rt].mx;
117         } else {
118             pushDown(rt);
119             int m=(l+r)>>1;
120             int res=-INF;
121             if(L<=m) res=max(res, doQuery(lson));
122             if(m<R) res=max(res, doQuery(rson));
123             return res;
124         }
125     }
126
127     int query(int L, int R) {
128         this->L=L; this->R=R;
129         return doQuery(1, n, 1);
130     }
131 #undef lson
132 #undef rson
133 #undef RUSH
134 } st;
135
136 int N;
137 int oval[MaxA], val[MaxA];
138 void init() {
139     edgeNum=0;
141 }
142 void addEdge(int u, int v, int w) {
145 }
146 namespace LCT {
147     int fa[MaxA];
148     int siz[MaxA];
149     int son[MaxA];
150     int dep[MaxA];
151     int top[MaxA];
152     int w[MaxA];
153     int id;
154     int e2p[MaxA];        ///边到点的映射
155
156     int dfs1(int u, int d) {
157         siz[u]=1; dep[u]=d; son[u]=-1;
158         for(int i=head[u]; ~i; i=edges[i].nt) {
159             Edge& e=edges[i];
160             if(e.v==fa[u]) continue;
161             e2p[(i>>1)+1]=e.v;        ///边到点的映射
162             fa[e.v]=u; oval[e.v]=e.w;    ///以点代边
163             siz[u]+=dfs1(e.v, d+1);
164             if(son[u]==-1 || siz[son[u]]<siz[e.v]) son[u]=e.v;
165         }
166         return siz[u];
167     }
168
169     void dfs2(int u, int tp) {
170         w[u]=++id; top[u]=tp;
171         if(~son[u]) dfs2(son[u], tp);
172         for(int i=head[u]; ~i; i=edges[i].nt) {
173             Edge& e=edges[i];
174             if(e.v==fa[u] || e.v==son[u]) continue;
175             dfs2(e.v, e.v);
176         }
177     }
178
179     void init() {
180         int root=1;
181         id=0; oval[root]=-INF; ///以点代边，根结点不代表任何边
182         fa[root]=-1;
183         dfs1(root, 0);
184         dfs2(root, root);
185         for(int i=1; i<=N; i++) {
186             val[w[i]]=oval[i];
187         }
188         st.build(N, val);
189     }
190
191     void change(int p, int v) {
192         st.change(w[e2p[p]], v);
193     }
194
195     int find(int u, int v, int op) {
196         int res=-INF;
197         int f1=top[u], f2=top[v];
198         while(f1!=f2) {
199             if(dep[f1]<dep[f2]) { swap(f1, f2); swap(u, v); }
200             if(op==0) res=max(res, st.query(w[f1], w[u]));
201             else st.negate(w[f1], w[u]);
202             u=fa[f1]; f1=top[u];
203         }
204         if(u==v) return res;
205         if(dep[u]>dep[v]) swap(u, v);
206         if(op==0) res=max(res, st.query(w[u]+1, w[v]));
207         else st.negate(w[u]+1, w[v]);
208         return res;
209     }
210 }
211 int main() {
212 #ifndef ONLINE_JUDGE
213     freopen("in", "r", stdin);
214     //freopen("out", "w", stdout);
215 #endif
216     int T;
217     scanf("%d", &T);
218     while(T--) {
219         scanf("%d", &N);
220         init();
221         for(int i=1; i<N; i++) {
222             int a, b, c;
223             scanf("%d%d%d", &a, &b, &c);
226         }
227
228         LCT::init();
229         char op[7];
230         while(scanf("%s", op), op[0]!=‘D‘) {
231             int a, b;
232             scanf("%d%d", &a, &b);
233             switch(op[0]) {
234                 case ‘C‘: LCT::change(a, b);
235                     break;
236                 case ‘N‘: LCT::find(a, b, 1);
237                     break;
238                 default: printf("%d\n", LCT::find(a, b, 0));
239             }
240         }
241     }
242     return 0;
243 }```

## BZOJ 2243: [SDOI2011]染色 树链剖分

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 1886  Solved: 752[Submit][Status] Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”.“222”和“1”. 请你写一个程序依次完成这m个操作. In

## bzoj 2243: [SDOI2011]染色 线段树区间合并+树链剖分

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 7925  Solved: 2975[Submit][Status][Discuss] Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”.“222”和“1”. 请你写一个程序依次完

## bzoj3694: 最短路（树链剖分/并查集）

bzoj1576的帮我们跑好最短路版本23333(双倍经验!嘿嘿嘿 这题可以用树链剖分或并查集写.树链剖分非常显然,并查集的写法比较妙,涨了个姿势,原来并查集的路径压缩还能这么用... 首先对于不在最短路径树上的边x->y,设t为最短路径树上lca(x,y),则t到y上的路径上的点i到根的距离都可以用h[x]+dis[x][y]+h[y]-h[i](h[]为深度)来更新,因为h[i]一定,只要让h[x]+dis[x][y]+h[y]最小就行,这里用树剖直接修改整条链上的数,就可以过了. 并查集的

## bzoj1036 树的统计（树链剖分+线段树）

1036: [ZJOI2008]树的统计Count Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 15120  Solved: 6141[Submit][Status][Discuss] Description 一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w.我们将以下面的形式来要求你对这棵树完成一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I

## SPOJ QTREE Query on a tree ——树链剖分 线段树

[题目分析] 垃圾vjudge又挂了. 树链剖分裸题. 垃圾spoj,交了好几次,基本没改动却过了. [代码](自带常数,是别人的2倍左右) #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define maxn 20005 int T,n,fr[maxn],h[maxn],to[maxn],ne[maxn]