【SPOJ Query on a tree 】 (树链剖分)

http://acm.hust.edu.cn/vjudge/problem/13013

题意：

有一棵N个节点的树（1<=N<=10000），N-1条边，边的编号为1~N-1，每条边有一个权值，要求模拟两种操作：

1：QUERY x y 求节点x和节点y之间的路径中权值最大的边。

2：CHANGE p k修改第p条边的权值为k。

【分析】

　　树链剖分裸题。。

　　【表示我一开始怎么TLE，后来怎么AC的并不知道。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<set>

 using namespace std;

 #define Maxn 10010

 #define INF 0x7fffffff

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

 struct node

 {

     int x,y,c,next;

 }t[*Maxn];int len;

 int first[Maxn];

 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;

 }

 char s[];

 int son[Maxn],dfn[Maxn],top[Maxn],cnt;

 int sm[Maxn],fa[Maxn],id[Maxn],dep[Maxn];

 void dfs1(int x,int f)

 {

     dep[x]=dep[f]+;

     sm[x]=;son[x]=;fa[x]=f;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)

     {

         int y=t[i].y;

         dfs1(y,x);

         sm[x]+=sm[y];

         if(son[x]==||sm[son[x]]<sm[y]) son[x]=y;

     }

 }

 void dfs2(int x,int tp)

 {

     dfn[x]=++cnt;top[x]=tp;

     if(son[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);

 }

 struct nnode

 {

     int l,r,lc,rc,mx;

 }tr[*Maxn];int tot;

 int build(int l,int r)

 {

     int x=++tot;

     tr[x].l=l;tr[x].r=r;

     int mid=(l+r)>>;

     if(l!=r)

     {

         tr[x].lc=build(l,mid);

         tr[x].rc=build(mid+,r);

     }

     tr[x].mx=-INF;

     return x;

 }

 void change(int x,int y,int z)

 {

     if(tr[x].l==tr[x].r)

     {

         tr[x].mx=z;

         return;

     }

     int mid=(tr[x].l+tr[x].r)>>;

     if(y<=mid) change(tr[x].lc,y,z);

     else change(tr[x].rc,y,z);

     tr[x].mx=mymax(tr[tr[x].lc].mx,tr[tr[x].rc].mx);

 }

 int query(int x,int l,int r)

 {

     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 query(tr[x].lc,l,r);

     else if(l>mid) return query(tr[x].rc,l,r);

     return mymax(query(tr[x].lc,l,mid),query(tr[x].rc,mid+,r));

 }

 int get_ans(int x,int y)

 {

     int mx=;

     while(top[x]!=top[y])

     {

         if(dep[top[x]]<dep[top[y]]) swap(x,y);

         mx=mymax(mx,query(,dfn[top[x]],dfn[x]));

         x=fa[top[x]];

     }

     if(x==y) return mx;

     if(dep[x]>dep[y]) swap(x,y);

     mx=mymax(mx,query(,dfn[x]+,dfn[y]));

     return mx;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         int n;

         scanf("%d",&n);

         len=;

         memset(first,,sizeof(first));

         for(int i=;i<n;i++)

         {

             int x,y,c;

             scanf("%d%d%d",&x,&y,&c);

             ins(x,y,c);ins(y,x,c);

         }

         dep[]=;dfs1(,);

         cnt=;dfs2(,);

         tot=;build(,n);

         for(int i=;i<=len;i+=)

         {

             if(fa[t[i].x]==t[i].y) id[(i+)/]=t[i].x;

             else id[(i+)/]=t[i].y;

             change(,dfn[id[(i+)/]],t[i].c);

         }

         while()

         {

             scanf("%s",s);

             if(s[]=='D') break;

             int x,y;

             scanf("%d%d",&x,&y);

             if(s[]=='C')

             {

                 change(,dfn[id[x]],y);

             }

             else

             {

                 printf("%d\n",get_ans(x,y));

             }

         }

     }

     return ;

 }

2017-01-21 11:45:00