蒟蒻刚学OI求助

#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
typedef long long ll;
int deep[maxn],fa[maxn],son[maxn],siz[maxn],id[maxn],top[maxn];
int head[maxn];
int w[maxn],wt[maxn];
int a[maxn*2],lazy[maxn*2];
int cnt,tot,res;
int n;
struct edge{
    int nxt,to,w;
}e[maxn*2];
void pushdown(int rt)
{
    a[rt*2]=a[rt*2+1]=lazy[rt*2]=lazy[rt*2+1]=lazy[rt];
    lazy[rt]=0;
}
void pushup(int k)
{
    //a[k]=max(a[k],max(a[k*2],a[k*2+1]));
    a[k]=max(a[k*2],a[k*2+1]);
}
void build(int root,int l,int r)
{
    if(l==r)
    {
        a[root]=wt[l];
        return ;
    }
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    pushup(root);
}
int query(int root,int lt,int rt,int L,int R)
{
    if(L==lt&&R==rt)
    {
        return a[rt];
    }
    else
    {
        int ans=0;
        int mid=(lt+rt)/2;
        if(lazy[root])
        pushdown(root);
        if(L<=mid)
        ans=max(ans,query(root*2,lt,mid,L,R));
        if(R>mid)
        ans=max(ans,query(root*2+1,mid+1,rt,L,R));
        return ans;
    }
}
void update(int root,int lt,int rt,int L,int R,int k)
{
    if(L>rt||R<lt)
    return ;
    if(L<=lt&&R>=rt)
    {
        a[rt]=lazy[rt]=k;
        return ;
    }
    int mid=(lt+rt)/2;
    if(lazy[root])
    pushdown(root);
    if(L<=mid)
    update(root*2,lt,mid,L,R,k);
    if(R>mid)
    update(root*2+1,mid+1,rt,L,R,k);
    pushup(root);
}
void add(int x,int y,int z)
{
    e[++tot].nxt=head[x];
    e[tot].to=y;
    e[tot].w=z;
    head[x]=tot;
}
void dfs1(int u,int f,int dep)
{
    deep[u]=dep;
    fa[u]=f;
    siz[u]=1;//标记每个非叶子节点的子树大小
    int maxson=-1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==f)
        continue;
        w[v]=e[i].w;
        dfs1(v,u,dep+1);
        siz[u]+=siz[v];
        if(siz[v]>maxson)
        {
            son[u]=v;
            maxson=siz[v];
        }
    }
}
void dfs2(int u,int topp)
{
    id[u]=++cnt;
    top[u]=topp;
    wt[cnt]=w[u];
    if(!son[u]) return ;
    dfs2(son[u],topp);
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==son[u]||v==fa[u]) continue;
        dfs2(v,v);
    }
}
int qrange(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])//当两个点不在同一条链上
    {
        if(deep[top[x]]<deep[top[y]])
        swap(x,y); //把x点改为所在链顶端的深度更深的那个点      
        ans=max(ans,query(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
    }
    //直到两个点处于一条链上
    if(id[x]>id[y])
    swap(x,y);
    ans=max(ans,query(1,1,n,id[x],id[y]));
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    while(1)
    {
        string s;
        cin>>s;
        if(s=="DONE")
        break;
        else if(s=="QUERY")
        {
            int a,b;
            cin>>a>>b;
            cout<<qrange(a,b)<<endl;
        }
        else if(s=="CHANGE")
        {
            int x,y;
            cin>>x>>y;
            x=deep[e[x*2-1].to]<deep[e[x*2].to]?e[x*2].to:e[x*2-1].to;
            update(1,1,n,id[x],id[x],y);
        }
    }
    return 0;
}