Qtree_testing

testing...

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int maxn=10010;
const int maxm=maxn*2;
const int maxu=maxn*4;
const int maxt=maxn*10;
const int oo=1993101215;
int test,n,e,indexs,dep,tot,lca,debug;
int id;  //重链编号 
int node;  //线段树节点 
int pre[maxm],other[maxm],last[maxm],w[maxm]; //建树
int dfsq[maxu],f[maxu][20],g[maxu][20],depq[maxu],pos[maxn];  //LCA相关 
int que[maxn],father[maxn],s[maxn],next[maxn],maxs[maxn],dis[maxn],a[maxn],fatherp[maxn];   //重链相关 
int left[maxt],right[maxt],leftnode[maxt],rightnode[maxt],root[maxn],data[maxt];   //线段树 
int pid[maxn];   //每个点所在的重链编号 
int order[maxn];  //每个点所在线段树的位置 
int ed[maxn];   //重链的结束节点
int link[maxn];  //节点上方的边是读入的第几条 
bool vis[maxn];

inline int MAX(int a,int b)
{
    if (a>b)return a; else return b;   
}

inline void add(int u,int v,int cost)
{
     e++;
     pre[e]=last[u];
     last[u]=e;
     other[e]=v;
     w[e]=cost;  
}

inline void init()
{
     int i,u,v,cost;
     memset(last,0,sizeof(last));
     e=0;
     scanf("%d\n",&n);
     for (i=1;i<n;i++)
     {
         scanf("%d%d%d\n",&u,&v,&cost);
         add(u,v,cost);
         add(v,u,cost);
     }       
}

inline void dfs(int u)
{
    dfsq[++indexs]=u;
    depq[indexs]=dep;
    if (pos[u]==0) pos[u]=indexs;  //记录首次出现的位置 
    vis[u]=true;
    for (int p=last[u];p;p=pre[p])
        if (vis[other[p]]==false)
        {
            dep++;
            dfs(other[p]);
            dep--;
            dfsq[++indexs]=u;  
            depq[indexs]=dep;
        }    
}

inline void st()
{
    //f[i][j]表示深搜序列i到j中最小的深度值
    //g[i][j]表示深度值最小的节点编号 
    int i,j;
    for (i=1;i<=indexs;i++)
    {
        f[i][0]=depq[i];
        g[i][0]=dfsq[i];
    }
    for (j=1;j<=int(log(indexs)/log(2));j++)
        for (i=1;i<=indexs-(1<<j)+1;i++)
            if (f[i][j-1]>f[i+(1<<(j-1))][j-1])
            {
                f[i][j]=f[i+(1<<(j-1))][j-1];
                g[i][j]=g[i+(1<<(j-1))][j-1];                              
            }
            else
            {
                f[i][j]=f[i][j-1];
                g[i][j]=g[i][j-1];    
            }
}

inline void getlca()
{
    indexs=0;
    dep=1;
    memset(vis,0,sizeof(vis));
    memset(pos,0,sizeof(pos));
    dfs(1);
    st();    
} 

inline int rmq(int x0,int y0)
{
    int l,r,t,k;
    l=pos[x0];
    r=pos[y0];
    if (l>r) {t=l;l=r;r=t;}
    k=int(log(r-l+1)/log(2));
    if (f[l][k]<f[r-(1<<k)+1][k])
        return g[l][k];
    else
        return g[r-(1<<k)+1][k];
}

inline void build(int l,int r,int &t)
{
    if (t==0)  t=++node;
    int mid=(l+r)/2;
    left[t]=l;
    right[t]=r;
    if (l==r)
    {
        data[t]=w[fatherp[a[l]]];
        return;        
    }
    build(l,mid,leftnode[t]);
    build(mid+1,r,rightnode[t]);
    data[t]=MAX(data[leftnode[t]],data[rightnode[t]]);
} 

inline int find(int l,int r,int t)
{
    if ((l==left[t])&&(r==right[t])) return data[t];
    int mid=(left[t]+right[t])/2;
    if (r<=mid) return find(l,r,leftnode[t]);
    if (l>=mid+1) return find(l,r,rightnode[t]);
    return MAX(find(l,mid,leftnode[t]),find(mid+1,r,rightnode[t]));    
}

inline void change(int x,int v,int t)
{
    if (left[t]==right[t])
    {
        data[t]=v;
        return ;
    }
    int mid=(left[t]+right[t])/2;
    if (x<=mid)
        change(x,v,leftnode[t]);
    if (x>=mid+1)
        change(x,v,rightnode[t]);
    data[t]=MAX(data[leftnode[t]],data[rightnode[t]]);
}

inline void bfs()  //求重链
{
    int i,j,l,r,q,p;
    memset(vis,0,sizeof(vis));
    memset(maxs,0,sizeof(maxs));
	memset(link,0,sizeof(link));
	memset(next,0,sizeof(next));
    node=0; id=0;
    memset(root,0,sizeof(root));
    memset(leftnode,0,sizeof(leftnode));
    memset(rightnode,0,sizeof(rightnode));
    
    memset(dis,0,sizeof(dis));
    memset(order,0,sizeof(order));
    memset(pid,0,sizeof(pid));
    memset(ed,0,sizeof(ed));
    memset(father,0,sizeof(father));
    memset(left,0,sizeof(left));
    memset(right,0,sizeof(right));
    memset(data,0,sizeof(data));
    l=0;
    r=1;
    que[r]=1;
    vis[1]=true;
    dis[1]=1;       //维护深度 
    while (l<r)
    {
         q=que[++l];
         for (p=last[q];p;p=pre[p])
             if (vis[other[p]]==false)
             {
                 vis[other[p]]=true;
                 que[++r]=other[p]; 
                 father[other[p]]=q;           //求得他的父亲节点编号   
                 fatherp[other[p]]=p;          //当前节点到父亲的边
                 dis[other[p]]=dis[q]+1;
                 link[(p+1)/2]=other[p];
             }
    }
    
    for (i=1;i<=n;i++) s[i]=1;
    for (i=n;i;i--) s[father[que[i]]]+=s[que[i]];
    
    for (i=1;i<=n;i++)
    {
        q=que[i];
        for (p=last[q];p;p=pre[p])
            if (dis[q]<dis[other[p]])
                if (s[other[p]]>maxs[q])
                {
                    maxs[q]=s[other[p]];
                    next[q]=other[p];
                }
    }

    memset(vis,0,sizeof(vis));
    for (i=1;i<=n;i++)
    {
        q=que[i];
        if (vis[q]==true) continue;
        id++;
        tot=0;
        ed[id]=q; 
        do
        {
              a[++tot]=q;
              vis[q]=true;
              pid[q]=id;
              order[q]=tot;
              q=next[q];      
        }   
        while (q!=0);
        build(1,tot,root[id]);
    }
    
    /*if (debug==2)
        for (i=1;i<=n;i++)
            if (dis[i]<dis[ed[pid[i]]])  
                 printf("?");*/
} 

inline int ask(int x,int y)   //从x节点一直到祖先y
{
    int ans=-oo; 
    //if (dt==1) printf("%d %d\n",x,y);
    while (x!=y)
    {
         //if (dt==1) printf("x : %d %d %d %d\n",x,y,dis[x],dis[y]);
         if (dis[ed[pid[x]]]<=dis[y])  //如果在一条链上 
         {
               ans=MAX(ans,find(order[y]+1,order[x],root[pid[x]]));
               break;                        
         }
         if (dis[ed[pid[x]]]>dis[y])  //如果不在一条链上 
         {
               ans=MAX(ans,find(1,order[x],root[pid[x]]));
           //    if (dt==1) printf("wo cao: %d %d\n",dis[x],dis[father[ed[pid[x]]]]);
               x=father[ed[pid[x]]];
               continue;                        
         }
    }
    return ans;
} 

inline void work()
{
    char s[30];
    int x,y;
    
    while (1)
    {
        scanf("%s",s);
        if (s[0]=='D') break;
        if (s[0]=='C')
        {
            scanf("%d%d\n",&x,&y);     
            change(order[link[x]],y,root[pid[link[x]]]);              
        } 
        if (s[0]=='Q')
        {
            scanf("%d%d\n",&x,&y);
            lca=rmq(x,y);
            printf("%d\n",MAX(ask(x,lca),ask(y,lca)));
        }
        
    }    
}

int main()
{
    scanf("%d\n",&test);
    while (test--)
    {
         debug++;
         init(); 
         getlca();
         bfs();
         work();
    }
    //system("pause");
    return 0;
}