树链剖分-spoj375

题意：给定一棵树，告诉了每条边的权值，然后给出两种操作：

(1)把第i条边的权值改为val

(2)询问a，b路径上权值最大的边

小心x==y的时候特判下

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
const int oo=10000010;
struct node{
    int w,u,v,next;
}a[40010];
int siz[20010],son[20010],begin[20010];
int deep[20010],top[20010],fa[20010];
int tot,b[20010],bh[20010];
/*void swap(int *x,int *y){
    int t=*x;
    *x=*y;*y=t;
    return;
}*/
int max(int x,int y){
    if(x>y)return x;
    else return y;
}
void add(int x,int y,int w){
    a[++tot].v=y;
    a[tot].u=x;
    a[tot].w=w;
    a[tot].next=begin[x];
    begin[x]=tot;
    return;
}
void dfs1(int u,int father,int d){

    fa[u]=father;
    deep[u]=d;
    siz[u]=1;
    int h=begin[u];
    while(h){
        if(a[h].v!=father){
            dfs1(a[h].v,u,d+1);
            siz[u]+=siz[a[h].v];
            if(siz[a[h].v]>siz[son[u]])
                son[u]=a[h].v;
        }
        h=a[h].next;
    }

    return;
}
void dfs2(int u,int tp){
    top[u]=tp;
    bh[u]=++tot;

    if(son[u]==0)
        return;
    dfs2(son[u],tp);
    int h=begin[u];
    while(h){
        if(a[h].v!=fa[u] && a[h].v!=son[u])
            dfs2(a[h].v,a[h].v);
        h=a[h].next;
    }
    return;
}
//线段树部分
struct node1{
    int l,r,max;
}tree[100010];

int home(int l,int r,int d){
    if(l==r){
        tree[d].l=l;
        tree[d].r=r;
        tree[d].max=b[l];
        return b[l];
    }
    tree[d].l=l;
    tree[d].r=r;
    int mid=(l+r)>>1;
    int x1=home(l,mid,d<<1);
    int x2=home(mid+1,r,d<<1|1);
    tree[d].max=max(x1,x2);
    return tree[d].max;
}
int change(int d,int x,int y){
    if(tree[d].l==tree[d].r){

        tree[d].max=y;
        return y;
    }
    int mid=(tree[d].l+tree[d].r)>>1;
    if(x<=mid)
        change(d<<1,x,y);
    else
        change(d<<1|1,x,y);
    tree[d].max=max(tree[d<<1].max,tree[d<<1|1].max);
    return tree[d].max;
}
int find(int d,int l,int r){
    if(l<=tree[d].l && r>=tree[d].r)
        return tree[d].max;
    int mid=(tree[d].l+tree[d].r)>>1;
    int x1=-oo,x2=-oo;
    if(l<=mid)
        x1=find(d<<1,l,r);
    if(r>mid)
        x2=find(d<<1|1,l,r);
    return max(x1,x2);
}
int query(int x,int y){
    int ans=-oo;
    while(top[x]!=top[y]){
        if(deep[top[y]]>deep[top[x]])
            std::swap(x,y);
        ans=max(ans,find(1,bh[top[x]],bh[x]));

        x=fa[top[x]];

    }
    if(deep[x]>deep[y])
        std::swap(x,y);
    if(x==y)return ans;
    ans=max(ans,find(1,bh[x]+1,bh[y]));
    return ans;
}
int mmp=0;
int main(){
    int t,i,n,x,y,w,c;
    char cc[20];
    scanf("%d",&t);
    while(t--){
    for(i=1;i<=10001;i++){
        siz[i]=0;son[i]=0;begin[i]=0;
    }
    tot=0;
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    int tot1=tot;
    tot=0;
    dfs1(1,1,1);
    tot=0;
    dfs2(1,1);
    for(i=1;i<=tot1;i++){
        if(deep[a[i].u]>deep[a[i].v])
            b[bh[a[i].u]]=a[i].w;
        else
            b[bh[a[i].v]]=a[i].w;
    }
    home(2,n,1);
    while(1){
        scanf("%s",cc);
        if(cc[0]=='D')
            break;
        scanf("%d%d",&x,&y);
        if(cc[0]=='Q'){
            if(x==y)printf("0\n");
            else printf("%d\n",query(x,y));
        }
        else{
            if(deep[a[x<<1].u]>deep[a[x<<1].v])
                change(1,bh[a[x<<1].u],y);
            else
                change(1,bh[a[x<<1].v],y);
        }
    }


    }

    return 0;
}