树链剖分专题

学习了一下树链剖分,找了几个有意义的题目训练一下

前4题是基础训练, A、B是AOV树(点记录信息) C、D是AOE树(边记录信息)

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

A、HDU 3966

题意:给你N个点M条边的一棵AOV树,有P次操作

操作分别是:‘I’:将C1到C2路径上的点增加K;

         ‘D’:将C1到C2路径上的点减少K;

         ‘Q’:问你C点上的权;

解:树链剖分基础题,需要注意的是杭电的服务器是windows的,代码中加入用下面这句话扩栈

#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  */
  9 #pragma comment(linker, "/STACK:1024000000,1024000000")
 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
 26 int head[MaxA], edgeNum;
 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() {
 62     memset(head, -1, sizeof(head));
 63     edgeNum=0;
 64 }
 65 void addEdge(int u, int v) {
 66     edges[edgeNum]=Edge(v, head[u]);
 67     head[u]=edgeNum++;
 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);
141             addEdge(a, b);
142             addEdge(b, a);
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 }

B、BZOJ 2243

题意:N个点的点AOV树,M次操作

操作:‘C a b c’:把节点a到节点b路径上所有点(包括a和b)都染成颜色c;

     ‘Q a b’:询问节点a到节点b(包括a和b)路径上的颜色段数量;

解:在A的基础上修改一下就好,需要理解树剖的分链而治

  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
 33 int head[MaxA], edgeNum;
 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;
140     memset(head, -1, sizeof(head));
141 }
142 void addEdge(int u, int v) {
143     edges[edgeNum]=Edge(v, head[u]);
144     head[u]=edgeNum++;
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);
226             addEdge(a, b);
227             addEdge(b, a);
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

题意:N个点的AOE树,q次操作,你开始在S点

操作:‘0 u’:你要去u点,问你你走过路径上的所有边的边权和;

   ‘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
 17 int head[MaxA], edgeNum;
 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() {
 57     memset(head, -1, sizeof(head));
 58     edgeNum=0;
 59 }
 60 void addEdge(int u, int v, int w) {
 61     edges[edgeNum]=Edge(v, head[u], w);
 62     head[u]=edgeNum++;
 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);
135             addEdge(a, b, c);
136             addEdge(b, a, 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

题意:N个结点的AOE树,各种操作~

操作:‘CHANGE i v’:将第i条边的权值变为w;

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

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

   ‘DONE’:操作结束

解:和C题差不多,只是需要修改树剖分之后的操作

  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
 27 int head[MaxA], edgeNum;
 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;
140     memset(head, -1, sizeof(head));
141 }
142 void addEdge(int u, int v, int w) {
143     edges[edgeNum]=Edge(v, head[u], w);
144     head[u]=edgeNum++;
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);
224             addEdge(a, b, c);
225             addEdge(b, a, 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 }

时间: 06-16

树链剖分专题的相关文章

专题训练之树链剖分

推荐几个博客:https://blog.csdn.net/y990041769/article/details/40348013 树链剖分详解 https://blog.csdn.net/ACdreamers/article/details/10591443 树链剖分原理 1.(HDOJ3966)http://acm.hdu.edu.cn/showproblem.php?pid=3966 题意:给一棵树,并给定各个点权的值,然后有3种操作: I C1 C2 K: 把C1与C2的路径上的所有点权值

bzoj4034 树上操作 树链剖分+线段树

题目传送门 题目大意: 有一棵点数为 N 的树,以点 1 为根,且树点有权.然后有 M 个操作,分为三种: 操作 1 :把某个节点 x 的点权增加 a . 操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a . 操作 3 :询问某个节点 x 到根的路径中所有点的点权和. 思路: 由于是在刷dfs序专题的时候碰到这题,所以思路被限制了,没想树链剖分的东西,没能做出来,后来发现了一个 大佬的博客,发现也是可以做的,但是这个做法看不懂...留坑 现在用树链剖分的方法,每个点的权值就是点本身

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]最小就行,这里用树剖直接修改整条链上的数,就可以过了. 并查集的

洛谷 P3384 【模板】树链剖分

题目描述 如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3: 格式: 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4: 格式: 4 x 表示求以x为根节点的子树内所有节点值之和 输入输出格式 输入格式: 第一行包含4个正整数N.M.R.P,分别表示树的结点个数.操作个数

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]

树链剖分简(单)介(绍)

树链剖分可以算是一种数据结构(一大堆数组,按照这个意思,主席树就是一大堆线段树).将一棵树分割成许多条连续的树链,方便完成一下问题: 单点修改(dfs序可以完成) 求LCA(各种乱搞也可以) 树链修改(修改任意树上两点之间的唯一路径) 树链查询 (各种操作)  前两个内容可以用其他方式解决,但是下面两种操作倍增.st表,dfs序就很难解决(解决当然可以解决,只是耗时长点而已).下面开始步入正题. 树链剖分的主要目的是分割树,使它成一条链,然后交给其他数据结构(如线段树,Splay)来进行维护.常