spoj375

题解：

树链剖分的模板题

具体代码详见网上的其他代码

代码：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

char s[];

int data[N],p[N],n,pos,fp[N],num[N];

int x,y,z,tot,top[N],T,e[N][],val[N],deep[N],son[N],fa[N],ne[N],fi[N],zz[N];

void jb(int x,int y)

{

    ne[++tot]=fi[x];

    fi[x]=tot;

    zz[tot]=y;

}

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

{

    deep[x]=z;

    fa[x]=y;

    for (int i=fi[x];i;i=ne[i])

     {

         int k=zz[i];

         if (k!=y)

          {

              dfs1(k,x,z+);

              num[x]+=num[k];

              if (son[x]==-||(num[son[x]]<num[k]))son[x]=k;

          }

     }

}

void dfs2(int x,int y)

{

    top[x]=y;

    if (son[x]!=-)

     {

         p[x]=pos++;

         fp[p[x]]=x;

         dfs2(son[x],y);

     }

    else

     {

         p[x]=pos++;

         fp[p[x]]=x;

         return;

     }

    for (int i=fi[x];i;i=ne[i])

     if (zz[i]!=son[x]&&zz[i]!=fa[x])

      dfs2(zz[i],zz[i]);

}

void pushup(int x)

{

    data[x]=max(data[x*],data[x*+]);

}

void build(int l,int r,int x)

{

    if (l==r)

     {

         data[x]=val[l];

         return;

     }

    int mid=(l+r)/;

    build(l,mid,x*);

    build(mid+,r,x*+);

    pushup(x);

}

void updata(int p,int q,int l,int r,int x)

{

    if (l==r)

     {

         data[x]=q;

         return;

     }

    int mid=(l+r)/;

    if (p<=mid)updata(p,q,l,mid,x*);

    else updata(p,q,mid+,r,x*+);

    pushup(x);

}

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

{

    if (x>r||y<l)return ;

    if (x<=l&&y>=r)return data[s];

    int mid=(l+r)/;

    return max(query(x,y,l,mid,s*),query(x,y,mid+,r,s*+));

}

int find(int x,int y)

{

    int f1=top[x],f2=top[y],temp=;

    while (f1!=f2)

     {

         if (deep[f1]<deep[f2])

          {

              swap(x,y);

              swap(f1,f2);

          }

         temp=max(temp,query(p[f1],p[x],,n,));

         x=fa[f1],f1=top[x];

     }

    if (x==y)return temp;

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

    return max(temp,query(p[son[x]],p[y],,n,));

}

int read()

{

    int x=;char c;

    for (;c<''||c>'';c=getchar());

    for (;c>=''&&c<='';c=getchar())x=x*+c-;

    return x;

}

int main()

{

    scanf("%d",&T);

    while (T--)

     {

         pos=;tot=;

         memset(fi,,sizeof fi);

         memset(son,-,sizeof son);

         memset(data,,sizeof data);

         scanf("%d",&n);

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

          {

              scanf("%d%d%d",&e[i][],&e[i][],&e[i][]);

              jb(e[i][],e[i][]);jb(e[i][],e[i][]);

          }

         dfs1(,,);

        dfs2(,);

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

         {

             if (deep[e[i][]]<deep[e[i][]])swap(e[i][],e[i][]);

             val[p[e[i][]]]=e[i][];

         }

        build(,n,);

         while (scanf("%s",&s))

          {

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

              x=read();y=read();

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

              else updata(p[e[x-][]],y,,n,);

          }

     }

    return ;

}