poj 3237 -- Tree

Tree

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 6842		Accepted: 1876

Description

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

　　　　　　　　　　　　　　　　　　　　[Submit] [Go Back] [Status] [Discuss]

题意：

　　给定一棵树和树上的边权，要求支持三种操作：

　　1.CHANGE a b 把第a条边的权值改成b

　　2.NEGATE a b 把a到b之间路径上的权值全部取反

3.QUERY a b 输出a到b之间路径上的最大边权

题解

　　树链剖分的思想还是很明显的，对于操作1，直接在线段树上单点修改就好了。对于操作2，区间修改+lazy标记，让标记累计，到传递标记的时候用mod 2来判断是否取反，如果要取反，那么MAX=-MIN MIN=-MAX(注意，这时的被刚才的-MIN覆盖，所以要提前存下原MAX)。操作2和操作3都要注意边权和点权之间的区别，避免写错。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<cstring>
  7 #include<vector>
  8 #include<queue>
  9 using namespace std;
 10 const int maxn=10050;
 11 const int inf=0x7fffffff;
 12 inline int read(){
 13     int x=0,f=1;char ch=getchar();
 14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 16     return x*f;
 17 }
 18 int T,N,M;
 19 int dep[maxn],siz[maxn],fa[maxn],son[maxn],top[maxn],id[maxn];
 20 int val[maxn];
 21 int num;
 22 char s[20];
 23 vector<int> to[maxn];
 24 struct E{
 25     int u,v,c;
 26 }e[maxn];
 27 
 28 inline void dfs1(int rt,int fath,int deep){
 29     dep[rt]=deep; siz[rt]=1; fa[rt]=fath; son[rt]=0;
 30     for(int i=0;i<to[rt].size();i++){
 31         int y=to[rt][i];
 32         if(y!=fa[rt]){
 33             dfs1(y,rt,deep+1);
 34             siz[rt]+=siz[y];
 35             if(siz[son[rt]]<siz[y]) son[rt]=y;
 36         }
 37     }
 38 }
 39 inline void dfs2(int rt,int tp){
 40     top[rt]=tp; id[rt]=++num;
 41     if(son[rt]!=0) dfs2(son[rt],tp);
 42     for(int i=0;i<to[rt].size();i++){
 43         int y=to[rt][i];
 44         if(y!=fa[rt]&&y!=son[rt]){
 45             dfs2(y,y);
 46         }
 47     }
 48 }
 49 
 50 struct node{
 51     int l,r;
 52     int MAX,MIN,lazy;
 53 }tree[maxn*8];
 54 inline void build(int rt,int l,int r){
 55     tree[rt].l=l; tree[rt].r=r;
 56     if(l==r){
 57         tree[rt].MAX=val[l]; tree[rt].MIN=val[l];
 58         tree[rt].lazy=0;
 59         return ;
 60     }
 61     int mid=(l+r)>>1;
 62     build(rt<<1,l,mid); build(rt<<1|1,mid+1,r);
 63     tree[rt].MAX=max(tree[rt<<1].MAX,tree[rt<<1|1].MAX);
 64     tree[rt].MIN=min(tree[rt<<1].MIN,tree[rt<<1|1].MIN);
 65 }
 66 inline void update_son(int rt){
 67     int d=tree[rt].lazy;
 68     if(d!=0){
 69         if(d%2==1) d=-1;
 70         else d=1;
 71         if(d==-1){
 72             int lsmx=tree[rt<<1].MAX,rsmx=tree[rt<<1|1].MAX;
 73             tree[rt<<1].MAX=-tree[rt<<1].MIN; tree[rt<<1].MIN=-lsmx;
 74             tree[rt<<1|1].MAX=-tree[rt<<1|1].MIN; tree[rt<<1|1].MIN=-rsmx;
 75         }
 76         tree[rt<<1].lazy+=tree[rt].lazy; tree[rt<<1|1].lazy+=tree[rt].lazy;
 77         tree[rt].lazy=0;
 78     }
 79 }
 80 inline void change(int rt,int v,int delta){
 81     if(tree[rt].l==tree[rt].r){
 82         tree[rt].MAX=delta; tree[rt].MIN=delta; tree[rt].lazy=0;
 83         return ;
 84     }
 85     update_son(rt);
 86     int mid=(tree[rt].l+tree[rt].r)>>1;
 87     if(v<=mid) change(rt<<1,v,delta);
 88     else change(rt<<1|1,v,delta);
 89     tree[rt].MAX=max(tree[rt<<1].MAX,tree[rt<<1|1].MAX);
 90     tree[rt].MIN=min(tree[rt<<1].MIN,tree[rt<<1|1].MIN);
 91 }
 92 inline void Negate(int rt,int l,int r){
 93     if(l<=tree[rt].l&&tree[rt].r<=r){
 94         int mx=tree[rt].MAX;
 95         tree[rt].MAX=-tree[rt].MIN; tree[rt].MIN=-mx;
 96         tree[rt].lazy++;
 97         return ;
 98     }
 99     update_son(rt);
100     int mid=(tree[rt].l+tree[rt].r)>>1;
101     if(l<=mid) Negate(rt<<1,l,r);
102     if(mid+1<=r) Negate(rt<<1|1,l,r);
103     tree[rt].MAX=max(tree[rt<<1].MAX,tree[rt<<1|1].MAX);
104     tree[rt].MIN=min(tree[rt<<1].MIN,tree[rt<<1|1].MIN);
105 }
106 inline int query(int rt,int l,int r){
107     if(l<=tree[rt].l&&tree[rt].r<=r){
108         return tree[rt].MAX;
109     }
110     update_son(rt);
111     int mid=(tree[rt].l+tree[rt].r)>>1;
112     int ans=-inf;
113     if(l<=mid) ans=max(ans,query(rt<<1,l,r));
114     if(mid+1<=r) ans=max(ans,query(rt<<1|1,l,r));
115     return ans;
116 }
117 inline void CHASK(int u,int v,int kin){
118     int tp1=top[u],tp2=top[v];
119     int ans=-inf;
120     while(tp1!=tp2){
121         if(dep[tp1]<dep[tp2]){
122             swap(tp1,tp2);
123             swap(u,v);
124         }
125         if(tp1==u){
126             if(kin==1)  Negate(1,id[tp1],id[u]);
127             else ans=max(ans,query(1,id[tp1],id[u]));
128             u=fa[tp1],tp1=top[u];
129         }
130         else{
131             if(kin==1)  Negate(1,id[tp1]+1,id[u]);
132             else ans=max(ans,query(1,id[tp1]+1,id[u]));
133             u=tp1,tp1=top[u];
134         }
135     }
136     if(dep[u]>dep[v]) swap(u,v);
137     if(kin==1) Negate(1,id[u]+1,id[v]);
138     else ans=max(ans,query(1,id[u]+1,id[v]));
139     if(kin==2) printf("%d
",ans);
140 }
141 inline void Clear(){
142     memset(dep,0,sizeof(dep)); memset(siz,0,sizeof(siz)); memset(fa,0,sizeof(fa));
143     memset(son,0,sizeof(son)); memset(top,0,sizeof(top)); memset(id,0,sizeof(id));
144     memset(val,0,sizeof(val));
145     for(int i=1;i<=N;i++) to[i].clear();
146     for(int i=1;i<=7*maxn;i++){
147         tree[i].l=tree[i].r=0;
148         tree[i].MAX=tree[i].MIN=tree[i].lazy=0;
149     }
150     N=0,M=0,num=0;
151 }
152 int main(){
153     T=read();
154     while(T--){
155         Clear();
156         N=read();
157         for(int i=1,u,v,c;i<=N-1;i++){
158             u=read(); v=read(); c=read();
159             e[i].u=u; e[i].v=v; e[i].c=c;
160             to[u].push_back(v); to[v].push_back(u);
161         }
162         dfs1(1,0,1); dfs2(1,1);
163     
164         for(int i=1;i<=N-1;i++){
165             int u=e[i].u,v=e[i].v,c=e[i].c;
166             if(fa[u]==v) val[id[u]]=c;
167             else val[id[v]]=c;
168         }
169         build(1,1,num);
170         for(;;){
171             scanf("%s",s);
172             int num,w,a,b;
173             if(s[0]=='C'){
174                 num=read(); w=read();
175                 if(fa[e[num].u]==e[num].v) change(1,id[e[num].u],w);
176                 else change(1,id[e[num].v],w);
177             }
178             else if(s[0]=='N'){
179                 a=read(); b=read();
180                 if(a!=b) CHASK(a,b,1);
181             }
182             else if(s[0]=='Q'){
183                 a=read(); b=read();
184                 if(a==b) printf("-2147483647
");
185                 else CHASK(a,b,2);
186             }
187             else if(s[0]=='D') break;
188         }
189     }
190     return 0;
191 }