POJ 3237 Tree(ツリー分割+セグメントツリー)

Descriptionの1本の木にはn個のノードがあり、n-1個のエッジがあり、各エッジに1個の重み値があり、3種類の操作CHANGE i v:i番目のエッジの重み値をv NEGATE a bに変更する:aからbまでのパス上のすべてのエッジの重み値を逆(x->-x)QUERY a bにする:aからbまでのパス上のすべてのエッジの重み値の最大値Inputを問い合わせる第1行の整数tは用例グループ数を表す.各組の使用例の第1行の1つの整数nは点数を表し、その後n-1行の各行の3つの整数a b cはa点とb点の間にcの重み値を持つ辺を表し、その後数行の各行に1回の操作を行い、DONEでこの組の使用例入力Outputがクエリ毎に終了する.クエリー結果Sample Input 1 3 1 1 2 2 2 3 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE Sample Output 1 3 Solutionツリー上のパスの問題を出力し、まずツリーチェーンを分割し、次にセグメントツリーを構築します.その後、線分ツリーの単点修正、区間更新、区間クエリーの問題が発生しましたCode

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 111111
#define INF 0x3f3f3f3f
struct Edge
{
    int to,next;
}E[2*maxn];
struct Tree
{
    int left,right,Min,Max,flag;//flag        
}T[4*maxn];
int t,n,Q,e[maxn][3],head[maxn],cnt,idx,size[maxn],fa[maxn],son[maxn],dep[maxn],top[maxn],id[maxn];
void init()
{
    cnt=idx=0;
    memset(head,-1,sizeof(head));
    dep[1]=fa[1]=size[0]=0;
    memset(son,0,sizeof(son));
}
void add(int u,int v)
{
    E[cnt].to=v;
    E[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs1(int u)
{
    size[u]=1;
    for(int i=head[u];~i;i=E[i].next)
    {
        int v=E[i].to;
        if(v!=fa[u])
        {
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs1(v);
            size[u]+=size[v];
            if(size[son[u]]<size[v]) son[u]=v;
        }
    }
}
void dfs2(int u,int topu)
{
    top[u]=topu;
    id[u]=++idx;
    if(son[u]) dfs2(son[u],top[u]);//       
    for(int i=head[u];~i;i=E[i].next)
    {
        int v=E[i].to;
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}
void build(int l,int r,int t)
{
    T[t].left=l;
    T[t].right=r;
    T[t].Min=T[t].Max=T[t].flag=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(l,mid,2*t);
    build(mid+1,r,2*t+1); 
}
void push_up(int t)
{
    T[t].Min=min(T[2*t].Min,T[2*t+1].Min);
    T[t].Max=max(T[2*t].Max,T[2*t+1].Max);
}
void push_down(int t)
{
    if(T[t].left==T[t].right)return ;
    if(T[t].flag)
    {
        int Min,Max;
        Min=T[2*t].Min,Max=T[2*t].Max;
        T[2*t].Max=-Min,T[2*t].Min=-Max;
        Min=T[2*t+1].Min,Max=T[2*t+1].Max;
        T[2*t+1].Max=-Min,T[2*t+1].Min=-Max;
        T[2*t].flag^=1,T[2*t+1].flag^=1;
        T[t].flag=0;
    }
}
void update(int x,int v,int t)//  x       v 
{
    if(T[t].left==x&&T[t].right==x)
    {
        T[t].Min=T[t].Max=v;
        T[t].flag=0;
        return ;
    }
    push_down(t);
    int mid=(T[t].left+T[t].right)>>1;
    if(x<=mid) update(x,v,2*t);
    else update(x,v,2*t+1);
    push_up(t);
}
int query(int l,int r,int t)//    [l,r]     
{
    if(T[t].left==l&&T[t].right==r)
        return T[t].Max;
    push_down(t);
    int mid=(T[t].left+T[t].right)>>1;
    if(r<=mid) return query(l,r,2*t);
    else if(l>mid) return query(l,r,2*t+1);
    else return max(query(l,mid,2*t),query(mid+1,r,2*t+1));
    push_up(t);
}
void reverse(int l,int r,int t)//   [l,r]     
{
    if(T[t].left==l&&T[t].right==r)
    {
        int Min,Max;
        Min=T[t].Min,Max=T[t].Max;
        T[t].Max=-Min,T[t].Min=-Max;
        T[t].flag^=1;
        return ;
    }
    push_down(t);
    int mid=(T[t].left+T[t].right)>>1;
    if(r<=mid) reverse(l,r,2*t);
    else if(l>mid) reverse(l,r,2*t+1);
    else
    {
        reverse(l,mid,2*t);
        reverse(mid+1,r,2*t+1);
    }
    push_up(t);
}
int Get_max(int u,int v)//  u->v        
{
    int top1=top[u],top2=top[v],ans=-INF;
    while(top1!=top2)
    {
        if(dep[top1]<dep[top2])
        {
            swap(top1,top2);
            swap(u,v);
        }
        ans=max(ans,query(id[top1],id[u],1));
        u=fa[top1];
        top1=top[u];
    }
    if(u==v)return ans;
    if(dep[u]>dep[v])swap(u,v);
    return max(ans,query(id[son[u]],id[v],1));
}
void Negate(int u,int v)// u->v         
{
    int top1=top[u],top2=top[v];
    while(top1!=top2)
    {
        if(dep[top1]<dep[top2])
        {
            swap(top1,top2);
            swap(u,v);
        }
        reverse(id[top1],id[u],1);
        u=fa[top1];
        top1=top[u];
    }
    if(u==v)return ;
    if(dep[u]>dep[v])swap(u,v);
    return reverse(id[son[u]],id[v],1);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();//    
        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
            //   
            add(e[i][0],e[i][1]);
            add(e[i][1],e[i][0]);
        }
        dfs1(1);//  dep,size,fa,son
        dfs2(1,1);//  top,id 
        build(1,idx,1);//  
        for(int i=1;i<n;i++)
        {
            if(dep[e[i][0]]>dep[e[i][1]])//  ,    id[i]   i     
                swap(e[i][0],e[i][1]);
            update(id[e[i][1]],e[i][2],1);
        }
        char op[11];
        while(~scanf("%s",op),op[0]!='D')
        {
            int u,v;
            scanf("%d%d",&u,&v);
            if(op[0]=='C')//     
                update(id[e[u][1]],v,1);
            else if(op[0]=='N')//     
                Negate(u,v);
            else//     
                printf("%d
",Get_max(u,v));
        } 
    }
    return 0;
}