SPOJ - QTREE Query on a tree题解

题目大意：

　　一棵树，有边权，有两个操作：1.修改一条边的权值；2.询问两点间路径上的边的权值的最大值。

思路：

　　十分裸的树链剖分+线段树，无非是边权要放到深度大的一端的点上，但是有两个坑爹的地方，改了好久：

　　1.数组定义10000和40000会TLE，要乘10；

　　2.以前的树剖求解的最后是这样的：

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

    return max(ans,MAX(,n,id[x],id[y],));

　　但是WA了，膜拜大神后发现这样就AC了：

    if (x==y) return ans;

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

    return max(ans,ask(,n,id[x]+,id[y],));

　　以前应该是错了。

代码：

 #include<cstdio>

 #include<iostream>

 using namespace std;

 const int M=;

 int n,cnt,t,p[M],hea[M],size[M],v[M],a[M],b[M],c[M],nex[M],dep[M],top[M],id[M],tree[M<<];

 char s[M]; bool vis[M];

 int read()

 {

     int x=; bool f=; char ch=getchar();

     while (ch<'' || ch>'') { if (ch=='-') f=; ch=getchar(); }

     while (ch>='' && ch<='') x=(x<<)+(x<<)+ch-,ch=getchar();

     return f?-x:x;

 }

 void add(int x,int y) { v[++cnt]=y,nex[cnt]=hea[x],hea[x]=cnt; }

 void dfs1(int x,int fa,int h)

 {

     size[x]=,dep[x]=h,p[x]=fa;

     for (int i=hea[x],y;i;i=nex[i])

         if ((y=v[i])^fa) dfs1(y,x,h+),size[x]+=size[y];

 }

 void dfs2(int x,int chain)

 {

     int i,k=,y;

     id[x]=++t,top[x]=chain;

     for (i=hea[x];i;i=nex[i])

         if (size[y=v[i]]>size[k] && y^p[x]) k=y;

     if (!k) return; dfs2(k,chain);

     for (i=hea[x];i;i=nex[i])

         if ((y=v[i])^p[x] && k^y) dfs2(y,y);

 }

 void push_up(int k) { tree[k]=max(tree[k<<],tree[k<<|]); }

 void change(int L,int R,int x,int val,int cur)

 {

     if (L==R) { tree[cur]=val; return; }

     int mid=L+R>>;

     if (x>mid) change(mid+,R,x,val,cur<<|);

     else change(L,mid,x,val,cur<<);

     push_up(cur);

 }

 int ask(int L,int R,int l,int r,int cur)

 {

     if (l<=L && R<=r) return tree[cur];

     int mid=L+R>>;

     if (r<=mid) return ask(L,mid,l,r,cur<<);

     else if (l>mid) return ask(mid+,R,l,r,cur<<|);

          else return max(ask(L,mid,l,mid,cur<<),ask(mid+,R,mid+,r,cur<<|));

 }

 int qry(int x,int y)

 {

     int ans=-;

     for (;top[x]^top[y];x=p[top[x]])

     {

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

         ans=max(ans,ask(,n,id[top[x]],id[x],));

     }

     if (x==y) return ans;

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

     return max(ans,ask(,n,id[x]+,id[y],));

 }

 int main()

 {

     for (int T=read(),i;T;--T)

     {

         n=read(),cnt=t=;

         for (i=;i<=n;++i) hea[i]=;

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

         {

             a[i]=read(),b[i]=read(),c[i]=read();

             add(a[i],b[i]),add(b[i],a[i]);

         }

         dfs1(,,),dfs2(,);

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

         {

             if (dep[a[i]]<dep[b[i]]) swap(a[i],b[i]);

             change(,n,id[a[i]],c[i],);

         }

         for (;;)

         {

             scanf("%s",s);

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

             int x=read(),y=read();

             if (s[]=='C') change(,n,id[a[x]],y,);

             if (s[]=='Q') printf("%d\n",qry(x,y));

         }

     }

     return ;

 }