树的维护

P1424 - [POJ3237]树的维护

Description

给你由N个结点组成的树。树的节点被编号为1到N，边被编号为1到N-1。每一条边有一个权值。然后你要在树上执行一系列指令。指令可以是如下三种之一：
CHANGE i v：将第i条边的权值改成v。
NEGATE a b：将点a到点b路径上所有边的权值变成其相反数。
QUERY a b：找出点a到点b路径上各边的最大权值。

Input

第一行有一个整数N（N<=10000）。
接下来N-1行每行有三个整数a,b,c，代表点a和点b之间有一条权值为c的边。这些边按照其编号从小到大给出。
接下来是若干条指令（不超过10^5条），都按照上面所说的格式。
最后一行是"DONE".

Output

对每个“QUERY”指令，输出一行，即路径上各边的最大权值。

Sample Input

3 

1 2 1 

2 3 2 

QUERY 1 2 

CHANGE 1 3 

QUERY 1 2 

DONE

Sample Output

1 

3

思路{

　　果断树链剖分，lazy等一系列取反操作等，思想很明确，但要注意细节，如修改时更新当前节点的值，重链端点记录等；

　　yade，调了我一上午！！！

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<queue>
  7 #include<ctime>
  8 #include<cmath>
  9 #include<map>
 10 #include<set>
 11 #define MAXX 100010
 12 #define rs ((o<<1)|1)
 13 #define ls (o<<1)
 14 #define INF 99999999
 15 using namespace std;
 16 struct ed{int nxt,to,c;}e[MAXX*4];
 17 struct t{int ma,mi;}tree[MAXX*4];
 18 int id[MAXX],top[MAXX],siz[MAXX],hson[MAXX],fa[MAXX],deep[MAXX];
 19 int head[MAXX],w[MAXX],sum,tot,n,nw[MAXX],lazy[MAXX*4];
 20 void add(int u,int v,int c){e[tot].nxt=head[u];e[tot].to=v;e[tot].c=c;head[u]=tot++;}
 21 void ADD(int u,int v,int c){add(u,v,c),add(v,u,c);}
 22 struct ac{
 23   int fr,to;
 24 }a[MAXX];
 25 void dfs1(int u,int faa){
 26   siz[u]=1,fa[u]=faa,deep[u]=deep[faa]+1;
 27   for(int i=head[u];i!=-1;i=e[i].nxt)if(e[i].to!=faa){
 28       w[e[i].to]=e[i].c;
 29       int v=e[i].to;dfs1(v,u);siz[u]+=siz[v];
 30       if(siz[hson[u]]<siz[v])hson[u]=v;
 31     }
 32 }
 33 void dfs2(int u,int toop){
 34   top[u]=toop;id[u]=++sum;nw[sum]=w[u];
 35   if(hson[u])dfs2(hson[u],toop);
 36   for(int i=head[u];i!=-1;i=e[i].nxt)if(e[i].to!=fa[u] && e[i].to!=hson[u])dfs2(e[i].to,e[i].to);
 37 }
 38 #define tr tree
 39 void down(int o){
 40   int xx=tree[rs].ma,yy=tree[rs].mi;
 41   if(lazy[o]==1) return;
 42   tr[rs].ma=(-1)*yy;tr[rs].mi=(-1)*xx;lazy[rs]*=(-1);
 43   xx=tree[ls].ma,yy=tree[ls].mi;
 44   tr[ls].ma=(-1)*yy;tr[ls].mi=(-1)*xx;lazy[ls]*=(-1);
 45   lazy[o]=1;return;
 46 }
 47 void build(int o,int l,int r){
 48   if(l==r){
 49     if(l!=1)tree[o].ma=nw[l],tree[o].mi=nw[l];
 50     else tree[o].ma=(-1)*INF,tree[o].mi=INF;
 51     return;
 52   }
 53   int mid=(l+r)>>1;
 54   build(ls,l,mid),build(rs,mid+1,r);
 55   tree[o].ma=max(tree[rs].ma,tree[ls].ma);
 56   tree[o].mi=min(tree[rs].mi,tree[ls].mi);
 57 }
 58 void update(int o,int l,int r,int p,int v){
 59   if(r!=l)down(o);
 60   if(l==r&&r==p){tree[o].ma=v,tree[o].mi=v;return;}   
 61   int mid=(l+r)>>1;
 62   if(mid<p)update(rs,mid+1,r,p,v);
 63   else update(ls,l,mid,p,v);
 64   tree[o].ma=max(tree[rs].ma,tree[ls].ma);
 65   tree[o].mi=min(tree[rs].mi,tree[ls].mi);
 66 }
 67 void qufan(int o,int l,int r,int ll,int rr){
 68   if(l!=r)down(o);
 69   if(l>=ll&&r<=rr){
 70     lazy[o]*=-1;
 71     int xx=tree[o].ma,yy=tree[o].mi;
 72     tree[o].mi=(-1)*xx,tree[o].ma=(-1)*yy;
 73     return;
 74   }
 75   int mid=(l+r)>>1;
 76   if(mid<ll)qufan(rs,mid+1,r,ll,rr);
 77   else if(rr<=mid)qufan(ls,l,mid,ll,rr);
 78   else qufan(ls,l,mid,ll,rr),qufan(rs,mid+1,r,ll,rr);
 79     tree[o].ma=max(tree[rs].ma,tree[ls].ma);
 80   tree[o].mi=min(tree[rs].mi,tree[ls].mi);
 81 }
 82 int querymax(int o,int l,int r,int ll,int rr){
 83   if(l!=r)down(o);
 84   if(l>=ll&&r<=rr)return tree[o].ma;
 85   int mid=(l+r)>>1;
 86   if(mid<ll)return querymax(rs,mid+1,r,ll,rr);
 87   else if(rr<=mid)return querymax(ls,l,mid,ll,rr);
 88   else return max(querymax(ls,l,mid,ll,rr),querymax(rs,mid+1,r,ll,rr));
 89 }
 90 int lca_max(int x,int y){
 91   int ans=-INF;
 92   while(top[x]!=top[y]){
 93     if(deep[top[x]]<deep[top[y]])swap(x,y);
 94     ans=max(ans,querymax(1,1,n,id[top[x]],id[x]));
 95     x=fa[top[x]];
 96   }
 97   if(deep[x]>deep[y])swap(x,y);
 98   if(x==y) return ans;
 99   ans=max(ans,querymax(1,1,n,id[x]+1,id[y]));
100   return ans;
101 }
102 void lca_ne(int x,int y){
103   while(top[x]!=top[y]){
104     if(deep[top[x]]<deep[top[y]])swap(x,y);
105     qufan(1,1,n,id[top[x]],id[x]);
106     x=fa[top[x]];
107   }
108   if(deep[x]>deep[y])swap(x,y);
109   if(x==y)return;
110   qufan(1,1,n,id[x]+1,id[y]);
111 }
112 int main(){
113   memset(head,-1,sizeof(head));
114   scanf("%d",&n);
115   for(int i=1;i<=n*4*2;i++) lazy[i]=1;
116   for(int i=1;i<n;++i){int u,v,c;scanf("%d%d%d",&u,&v,&c);ADD(u,v,c);a[i].fr=u;a[i].to=v;}
117   string ss;dfs1(1,0),dfs2(1,1);
118   build(1,1,n);
119   while(1){
120     cin>>ss;
121     if(ss[0]=='D') break;
122     if(ss[0]=='Q'){
123       int u,v;
124       scanf("%d%d",&u,&v);
125       printf("%d
",lca_max(u,v));
126     }
127     else
128       if(ss[0]=='C'){
129     int x,y;scanf("%d%d",&x,&y);
130     int fr=a[x].fr,to=a[x].to;
131         if(deep[fr]>deep[to])swap(fr,to);
132     update(1,1,n,id[to],y);
133       }
134       else {
135     int x,y;scanf("%d%d",&x,&y);
136     lca_ne(x,y);
137       }
138   }
139   return 0;
140 }

}