Tree(树链剖分+线段树延迟标记)

佚名 6年前 (2018-09-25) 算法 1089人围观抢沙发百度已收录

Tree

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 12268		Accepted: 3159

Description

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

`CHANGE` i v	Change the weight of the ith edge to v
`NEGATE` a b	Negate the weight of every edge on the path from a to b
`QUERY` a b	Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Sample Output

1
3

Source

POJ Monthly--2007.06.03, Lei, Tao 这题的延迟标记是进行取反操作，不是按位取反。。。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<cstdio>
  6 #include<algorithm>
  7 #include<vector>
  8 #define maxn 200005
  9 #define lson l,mid,rt<<1
 10 #define rson mid+1,r,rt<<1|1
 11 #define mem(a,b) memset(a,b,sizeof(a))
 12 using namespace std;
 13 
 14 struct Tree{;
 15     int Max,Min;
 16 }tree[maxn<<3];
 17 int lazy[maxn<<3];
 18 int n;
 19 int dep[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn],top[maxn],cnt;
 20 int co,head[maxn];
 21 struct Edge {
 22     int to, next;
 23 }edge[maxn];
 24 
 25 void Swap(int &x,int &y){
 26     int t=x;x=-y;y=-t;
 27 }
 28 
 29 void addedge(int u, int v) {
 30     edge[cnt].to = v;
 31     edge[cnt].next = head[u];
 32     head[u] = cnt++;
 33 }
 34 struct sair{
 35     int x,y,len;
 36 }p[maxn];
 37 
 38 void pushdown(int rt){
 39     if(lazy[rt]){
 40       /*  tree[rt<<1].Max+=1;
 41         tree[rt<<1|1].Max+=1;
 42         tree[rt<<1].Min+=1;
 43         tree[rt<<1|1].Min+=1;*/
 44         Swap(tree[rt<<1].Max,tree[rt<<1].Min);
 45         Swap(tree[rt<<1|1].Max,tree[rt<<1|1].Min);
 46         lazy[rt<<1]^=1;
 47         lazy[rt<<1|1]^=1;
 48         lazy[rt]=0;
 49     }
 50 }
 51 
 52 void pushup(int rt){
 53     tree[rt].Max=max(tree[rt<<1].Max,tree[rt<<1|1].Max);
 54     tree[rt].Min=min(tree[rt<<1].Min,tree[rt<<1|1].Min);
 55 }
 56 
 57 void build(int l,int r,int rt){
 58     lazy[rt]=0;
 59     if(l==r){
 60         tree[rt].Max=tree[rt].Min=0;
 61         return;
 62     }
 63     int mid=(l+r)/2;
 64     build(lson);
 65     build(rson);
 66     pushup(rt);
 67 }
 68 
 69 void add(int L,int R,int k,int l,int r,int rt){
 70     if(L<=l&&R>=r){
 71         tree[rt].Max=tree[rt].Min=k;
 72         return;
 73     }
 74     pushdown(rt);
 75     int mid=(l+r)/2;
 76     if(L<=mid) add(L,R,k,lson);
 77     if(R>mid) add(L,R,k,rson);
 78     pushup(rt);
 79 }
 80 
 81 void nega(int L,int R,int l,int r,int rt){
 82     if(L<=l&&R>=r){
 83         Swap(tree[rt].Max,tree[rt].Min);
 84         lazy[rt]^=1;
 85         return;
 86     }
 87     pushdown(rt);
 88     int mid=(l+r)/2;
 89     if(L<=mid) nega(L,R,lson);
 90     if(R>mid) nega(L,R,rson);
 91     pushup(rt);
 92 }
 93 
 94 int query(int L,int R,int l,int r,int rt){
 95     if(L<=l&&R>=r){
 96         return tree[rt].Max;
 97     }
 98     pushdown(rt);
 99     int mid=(l+r)/2;
100     int ans=-0x3f3f3f3f;
101     if(L<=mid) ans=max(ans,query(L,R,lson));
102     if(R>mid) ans=max(ans,query(L,R,rson));
103     pushup(rt);
104     return ans;
105 }
106 
107 void dfs1(int now,int f,int deep){
108     dep[now]=deep;
109     siz[now]=1;
110     fa[now]=f;
111     int maxson=-1;
112     for(int i=head[now];~i;i=edge[i].next){
113         if(edge[i].to != fa[now]) {
114             dfs1(edge[i].to,now,deep+1);
115             siz[now]+=siz[edge[i].to];
116             if(siz[edge[i].to]>maxson){
117                 maxson=siz[edge[i].to];
118                 son[now]=edge[i].to;
119             }
120         }
121     }
122 }
123 
124 void dfs2(int now,int topp){
125     id[now]=++cnt;
126     top[now]=topp;
127     if(!son[now]) return;
128     dfs2(son[now],topp);
129     for(int i=head[now];~i;i=edge[i].next){
130         int vvv = edge[i].to;
131         if(vvv==son[now]||vvv==fa[now]) continue;
132         dfs2(vvv,vvv);
133     }
134 }
135 
136 int qRange(int x,int y){
137     int t1 = top[x], t2 = top[y];
138     int res = -0x3f3f3f3f;
139     while(t1 != t2) {
140         if(dep[t1] < dep[t2]) {
141             swap(t1, t2); swap(x, y);
142         }
143         res = max(res,query(id[t1], id[x], 1, n, 1));
144         x = fa[t1]; t1 = top[x];
145     }
146     if(x == y) return res;
147     if(dep[x] > dep[y]) swap(x, y);
148     return max(res,query(id[son[x]], id[y], 1, n, 1));
149 }
150 
151 void NRange(int x,int y){
152     int t1 = top[x], t2 = top[y];
153     while(t1 != t2) {
154         if(dep[t1] < dep[t2]) {
155             swap(t1, t2); swap(x, y);
156         }
157         nega(id[t1],id[x],1,n,1);
158         x = fa[t1]; t1 = top[x];
159     }
160     if(x == y) return;
161     if(dep[x] > dep[y]) swap(x, y);
162     nega(id[son[x]],id[y],1,n,1);
163 }
164 
165 void addRange(int x,int y,int k){
166     while(top[x]!=top[y]){
167         if(dep[top[x]]<dep[top[y]]) swap(x,y);
168         add(id[top[x]],id[x],k,1,n,1);
169         x=fa[top[x]];
170     }
171     if(dep[x]>dep[y]) swap(x,y);
172     add(id[x],id[y],k,1,n,1);
173 }
174 
175 int main(){
176     int m,r;
177     int t;
178     scanf("%d",&t);
179     while(t--){
180         scanf("%d",&n);
181         memset(head, -1, sizeof head);
182         mem(dep,0);
183         mem(fa,0);
184         mem(siz,0);
185         mem(son,0);
186         mem(id,0);
187         mem(top,0);
188         int z,x,y;
189         co=0;
190         cnt=0;
191         for(int i=1;i<n;i++){
192             scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].len);
193             addedge(p[i].x,p[i].y);
194             addedge(p[i].y,p[i].x);
195         }
196         cnt=0;
197         int xx;
198         dfs1(1,0,1);
199         dfs2(1,1);
200         build(1,n,1);
201         for(int i=1;i<n;i++){
202             if(dep[p[i].x]<dep[p[i].y]) xx=p[i].y;
203             else xx=p[i].x;
204             addRange(xx,xx,p[i].len);
205         }
206         char pos[15];
207         while(~scanf("%s",pos)){
208             if(pos[0]=='D') break;
209             scanf("%d %d",&x,&y);
210             if(pos[0]=='C'){
211                 p[x].len=y;
212                 if(dep[p[x].x]<dep[p[x].y]) xx=p[x].y;
213                 else xx=p[x].x;
214                 addRange(xx,xx,p[x].len);
215             }
216             else if(pos[0]=='N'){
217                 NRange(x,y);
218             }
219             else if(pos[0]=='Q'){
220                 printf("%d\n",qRange(x,y));
221             }
222         }
223     }
224 }