【POJ3237】Tree（树链剖分+线段树）

Description

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 throughN − 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:

CHANGEiv	Change the weight of the ith edge to v
NEGATEab	Negate the weight of every edge on the path from a to b
QUERYab	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

【题意】

指定一颗树上有3个操作：

　　询问操作,询问a点和b点之间的路径上最长的那条边的长度；

　　取反操作，将a点和b点之间的路径权值都取相反数；

　　变化操作，把某条边的权值x变成指定的值。

【分析】

　　人生第一道树剖题，调了好久啊，200+的代码还打了对拍= =

　　就是裸的树链剖分+线段树啦。

　　就是线段树打得不够熟练所以调了那么久，lazy标记不大会用~~

　　

　　树剖的主要过程就是两次的dfs，第一次求fa，第二次求top。询问过程就是一直跳，跳到两个东西在一条重链上去。

　　因为某种特殊性质，所以他很快。。

代码如下：

 #include<cstdio>
 #include<cstdlib>
 #include<cstring>
 #include<iostream>
 #include<algorithm>
 using namespace std;
 #define Maxn 10010
 #define INF 100000000

 int fa[Maxn],first[Maxn],size[Maxn],dep[Maxn],son[Maxn];
 int w[Maxn],top[Maxn];int wl;
 int b[Maxn][];

 struct node
 {
     int x,y,c,next;
 }t[*Maxn];int len;

 struct nnode
 {
     int l,r,lc,rc,mx,mn;
     bool lazy;
 }tr[*Maxn];int tl;

 int mymax(int x,int y) {return x>y?x:y;}
 int mymin(int x,int y) {return x<y?x:y;}

 void ins(int x,int y,int c)
 {
     t[++len].x=x;t[len].y=y;t[len].c=c;
     t[len].next=first[x];first[x]=len;
 }

 void dfs1(int x,int f)
 {
     fa[x]=f;dep[x]=dep[f]+;size[x]=;
     son[x]=;
     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
     {
         dfs1(t[i].y,x);
         size[x]+=size[t[i].y];
         if(size[t[i].y]>size[son[x]]) son[x]=t[i].y;
     }
 }

 void dfs2(int x,int tp)
 {
     w[x]=++wl;
     top[x]=tp;
     if(size[x]!=) dfs2(son[x],tp);
     for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x]&&t[i].y!=son[x])
     {
         dfs2(t[i].y,t[i].y);
     }
 }

 int build(int l,int r)
 {
     int x=++tl;
     tr[x].l=l;tr[x].r=r;tr[x].mx=-INF;tr[x].mn=INF;tr[x].lazy=;
     if(l!=r)
     {
         int mid=(l+r)>>;
         tr[x].lc=build(l,mid);
         tr[x].rc=build(mid+,r);
     }
     return x;
 }

 void upd(int x)
 {
     if(!tr[x].lazy) return;
     tr[x].lazy=;
     int a=tr[x].mx;
     tr[x].mx=-tr[x].mn;tr[x].mn=-a;
     if(tr[x].l==tr[x].r) return;
     tr[tr[x].lc].lazy=!tr[tr[x].lc].lazy;
     tr[tr[x].rc].lazy=!tr[tr[x].rc].lazy;
 }

 void change(int x,int y,int c)
 {
     upd(x);
     if(tr[x].l==tr[x].r)
     {
         tr[x].mx=c;
         tr[x].mn=c;
         return;
     }
     int mid=(tr[x].l+tr[x].r)>>;
     if(y<=mid) change(tr[x].lc,y,c);
     else change(tr[x].rc,y,c);
     upd(tr[x].lc);upd(tr[x].rc);
     tr[x].mx=mymax(tr[tr[x].lc].mx,tr[tr[x].rc].mx);
     tr[x].mn=mymin(tr[tr[x].lc].mn,tr[tr[x].rc].mn);
 }

 int qtree(int x,int l,int r)
 {
     upd(x);
     if(tr[x].l==l&&tr[x].r==r) return tr[x].mx;
     int mid=(tr[x].l+tr[x].r)>>;
     if(r<=mid) return qtree(tr[x].lc,l,r);
     if(l>mid) return qtree(tr[x].rc,l,r);
     return mymax(qtree(tr[x].lc,l,mid),qtree(tr[x].rc,mid+,r));
 }

 int query(int x,int y)
 {
     int tmp=-INF;
     int f1=top[x],f2=top[y];
     while(f1!=f2)
     {
         if(dep[f1]<dep[f2])
         {
             swap(f1,f2);
             swap(x,y);
         }
         tmp=mymax(qtree(,w[f1],w[x]),tmp);
         x=fa[f1];
         f1=top[x];
     }
     if(x==y) return tmp;
     if(dep[x]<dep[y]) swap(x,y);
     return mymax(tmp,qtree(,w[son[y]],w[x]));
 }

 void change2(int x,int l,int r)
 {
     upd(x);
     if(tr[x].l==l&&tr[x].r==r)
     {
         tr[x].lazy=!tr[x].lazy;
         upd(x);
         return;
     }
     int mid=(tr[x].l+tr[x].r)>>;
     if(r<=mid) change2(tr[x].lc,l,r);
     else if(l>mid) change2(tr[x].rc,l,r);
     else
     {
         change2(tr[x].lc,l,mid);
         change2(tr[x].rc,mid+,r);
     }
     upd(tr[x].lc);upd(tr[x].rc);
     tr[x].mx=mymax(tr[tr[x].lc].mx,tr[tr[x].rc].mx);
     tr[x].mn=mymin(tr[tr[x].lc].mn,tr[tr[x].rc].mn);
 }

 void negate1(int x,int y)
 {
     int f1=top[x],f2=top[y];
     while(f1!=f2)
     {
         if(dep[f1]<dep[f2])
         {
             swap(f1,f2);
             swap(x,y);
         }
         change2(,w[f1],w[x]);
         x=fa[f1];
         f1=top[x];
     }
     if(x==y) return;
     if(dep[x]<dep[y]) swap(x,y);
     change2(,w[son[y]],w[x]);
 }

 int main()
 {
     int T;
     scanf("%d",&T);
     while(T--)
     {
         int n;
         scanf("%d",&n);
         memset(first,,sizeof(first));
         len=;
         for(int i=;i<n;i++)
         {
             int x,y,c;
             scanf("%d%d%d",&x,&y,&c);
             b[i][]=x;b[i][]=y;b[i][]=c;
             ins(x,y,c);ins(y,x,c);
         }
         dep[]=;size[]=;
         dfs1(,);wl=;
         dfs2(,);
         char s[];
         tl=;
         build(,wl);
         for(int i=;i<n;i++)
         {
             if(dep[b[i][]]<dep[b[i][]]) swap(b[i][],b[i][]);
             change(,w[b[i][]],b[i][]);
         }
         while()
         {
             scanf("%s",s);
             if(s[]=='D') break;
             if(s[]=='Q')
             {
                 int x,y;
                 scanf("%d%d",&x,&y);
                 printf("%d\n",query(x,y));
             }
             else if(s[]=='C')
             {
                 int x,y;
                 scanf("%d%d",&x,&y);
                 change(,w[b[x][]],y);//单点修改
             }
             else
             {
                 int x,y;
                 scanf("%d%d",&x,&y);
                 negate1(x,y);
             }
         }
     }
     return ;
 }

[POJ3237]

2016-05-08 14:50:31