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&lt;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&lt;=n;i++) s[i]=1;
for (i=n;i;i--) s[father[que[i]]]+=s[que[i]];

for (i=1;i&lt;=n;i++)
{
    q=que[i];
    for (p=last[q];p;p=pre[p])
        if (dis[q]&lt;dis[other[p]])
            if (s[other[p]]&gt;maxs[q])
            {
                maxs[q]=s[other[p]];
                next[q]=other[p];
            }
}

memset(vis,0,sizeof(vis));
for (i=1;i&lt;=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&lt;=n;i++)
        if (dis[i]&lt;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",&amp;x,&amp;y);     
        change(order[link[x]],y,root[pid[link[x]]]);              
    } 
    if (s[0]=='Q')
    {
        scanf("%d%d\n",&amp;x,&amp;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;
}

testing...