【POJ3237】Tree

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N ? 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N ? 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

For each “QUERY” instruction, output the result on a separate line.

#include <stdio.h>
#include <string.h>
#include <iostream>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const int maxn=10010;
int n,cnt,tot;
int sm[maxn<<2],sn[maxn<<2],tag[maxn<<2];
int to[maxn<<1],next[maxn<<1],val[maxn<<1],v[maxn],u[maxn],fa[maxn],head[maxn];
int deep[maxn],size[maxn],son[maxn],p[maxn],top[maxn];
char str[10];
int readin()
{
    int ret=0,sig=1;    char gc;
    while(gc<‘0‘||gc>‘9‘)    sig=(gc==‘-‘)?-1:1,gc=getchar();
    while(gc>=‘0‘&&gc<=‘9‘)    ret=ret*10+gc-‘0‘,gc=getchar();
    return ret*sig;
}
void add(int a,int b,int c)
{
    to[cnt]=b;
    val[cnt]=c;
    next[cnt]=head[a];
    head[a]=cnt++;
}
void dfs1(int x)
{
    size[x]=1;
    for(int i=head[x];i!=-1;i=next[i])
    {
        if(to[i]!=fa[x])
        {
            fa[to[i]]=x;
            u[to[i]]=val[i];
            deep[to[i]]=deep[x]+1;
            dfs1(to[i]);
            size[x]+=size[to[i]];
            if(size[to[i]]>size[son[x]])    son[x]=to[i];
        }
    }
}
void dfs2(int x,int tp)
{
    top[x]=tp;
    p[x]=++tot;
    v[p[x]]=u[x];
    if(son[x])    dfs2(son[x],tp);
    for(int i=head[x];i!=-1;i=next[i])
        if(to[i]!=son[x]&&to[i]!=fa[x])
            dfs2(to[i],to[i]);
}
void pushup(int x)
{
    sm[x]=max(sm[lson],sm[rson]);
    sn[x]=min(sn[lson],sn[rson]);
}
void pushdown(int x)
{
    if(tag[x])
    {
        swap(sm[lson],sn[lson]),swap(sm[rson],sn[rson]);
        sm[lson]=-sm[lson],sn[lson]=-sn[lson],sm[rson]=-sm[rson],sn[rson]=-sn[rson];
        tag[lson]^=1,tag[rson]^=1;
        tag[x]=0;
    }
}
void build(int l,int r,int x)
{
    if(l==r)
    {
        sm[x]=sn[x]=v[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,lson),build(mid+1,r,rson);
    pushup(x);
}
void updata(int l,int r,int x,int a,int b)
{
    if(l==r)
    {
        sm[x]=sn[x]=b;
        return ;
    }
    pushdown(x);
    int mid=l+r>>1;
    if(a<=mid)    updata(l,mid,lson,a,b);
    else    updata(mid+1,r,rson,a,b);
    pushup(x);
}
void upgate(int l,int r,int x,int a,int b)
{
    if(a<=l&&r<=b)
    {
        tag[x]^=1;
        swap(sm[x],sn[x]);
        sm[x]=-sm[x],sn[x]=-sn[x];
        return ;
    }
    pushdown(x);
    int mid=l+r>>1;
    if(b<=mid)    upgate(l,mid,lson,a,b);
    else if(a>mid)    upgate(mid+1,r,rson,a,b);
    else    upgate(l,mid,lson,a,b),upgate(mid+1,r,rson,a,b);
    pushup(x);
}
int query(int l,int r,int x,int a,int b)
{
    if(a<=l&&r<=b)    return sm[x];
    pushdown(x);
    int mid=l+r>>1;
    if(b<=mid)    return query(l,mid,lson,a,b);
    if(a>mid)    return query(mid+1,r,rson,a,b);
    return max(query(l,mid,lson,a,b),query(mid+1,r,rson,a,b));
}
void change()
{
    int x=readin(),y=readin();
    updata(1,n,1,max(p[to[x*2-2]],p[to[x*2-1]]),y);
}
void fan()
{
    int x=readin(),y=readin();
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])    swap(x,y);
        upgate(1,n,1,p[top[x]],p[x]);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])    swap(x,y);
    if(x!=y)    upgate(1,n,1,p[x]+1,p[y]);
}
void getmax()
{
    int x=readin(),y=readin(),ans=1<<31;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])    swap(x,y);
        ans=max(ans,query(1,n,1,p[top[x]],p[x]));
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])    swap(x,y);
    if(x!=y)    ans=max(ans,query(1,n,1,p[x]+1,p[y]));
    printf("%d\n",ans);
}
void work()
{
    n=readin();
    memset(head,-1,sizeof(head));
    memset(son,0,sizeof(son));
    memset(fa,0,sizeof(fa));
    memset(tag,0,sizeof(tag));
    cnt=tot=0;
    int i,a,b,c;
    for(i=1;i<n;i++)
    {
        a=readin(),b=readin(),c=readin();
        add(a,b,c),add(b,a,c);
    }
    deep[1]=1;
    dfs1(1);
    dfs2(1,1);
    build(1,n,1);
    while(scanf("%s",str))
    {
        switch(str[0])
        {
            case ‘C‘:change();    break;
            case ‘N‘:fan();    break;
            case ‘Q‘:getmax();    break;
            case ‘D‘:return ;
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)    work();
    return 0;
}