水题求救

https://www.luogu.com.cn/record/135397522

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
int deg[N],maxlen[N],maxlenson[N],id[N],v[N],ftop[N],faa[N],fid[N];
int ind,cnt;
vector<int> ma[N];

void dfs(int u,int fa)
{
    faa[u]=fa;
    deg[u]=deg[fa]+1;
    for(int i=0;i<ma[u].size();i++)
    {
        if(ma[u][i]==fa) continue;
        dfs(ma[u][i],u);
        if(maxlen[u]<maxlen[ma[u][i]])
        {
            maxlen[u]=maxlen[ma[u][i]];
            maxlenson[u]=ma[u][i];
        }
    }
    maxlen[u]++;
}

void dfs2(int u,int fa)
{
    id[u]=++ind;
    fid[ind]=u;
    if(maxlenson[u])
    {
        ftop[maxlenson[u]]=ftop[u];
        dfs2(maxlenson[u],u);
    }
    for(int i=0;i<ma[u].size();i++)
    {
        if(ma[u][i]==fa||ma[u][i]==maxlenson[u]) continue;
        ftop[ma[u][i]]=ma[u][i];
        dfs2(ma[u][i],u);
    }
}

class segment_tree{
public:
    struct tree{
        int l,r,maxx;
        void clear(){ l=r=maxx=0;}
    };

    vector<tree> tr;

    segment_tree(int l,int r){
        tree temp;
        temp.clear();
        tr.resize(N*4,temp);
        build(1,l,r);
    }

    void pushup(int k){tr[k].maxx=max(tr[k<<1].maxx,tr[k<<1|1].maxx);}

    void build(int k,int l,int r)
    {
        tr[k].l=l,tr[k].r=r;
        if(l==r) return void(tr[k].maxx=v[fid[l]]);
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        pushup(k);
    }

    void change(int k,int pos,int index)
    {
        if(tr[k].l==tr[k].r) return void(tr[k].maxx=pos);
        int mid=(tr[k].l+tr[k].r)>>1;
        if(index<=mid) change(k<<1,pos,index);
        else if(mid<index) change(k<<1|1,pos,index);
        pushup(k);
    } 

    int query(int k,int l,int r)
    {
        if(l<=tr[k].l&&tr[k].r<=r) return tr[k].maxx;
        int mid=(tr[k].l+tr[k].r)>>1,res=0;
        if(l<=mid) res=max(res,query(k<<1,l,r));
        if(mid<r) res=max(res,query(k<<1|1,l,r));
        return res;
    }
};
signed main()
{
    cin >> n;
//  for(int i=1;i<=n;i++) v[i]=-2e9;
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        v[n+i]=z;
        ma[x].push_back(n+i);
        ma[y].push_back(n+i);
        ma[n+i].push_back(x);
        ma[n+i].push_back(y);
    }
    ftop[1]=1;
    dfs(1,0);
    dfs2(1,0);
    segment_tree tree(1,n+n-1);
//  for(int i=1;i<=n+n-1;i++) printf("%d ",id[i]); 
//  printf("\n");
//  for(int i=1;i<=n+n-1;i++) printf("%d ",fid[i]);  
//  printf("\n");
//  build(1,1,ind);

    while(1)
    {
        string opt;
        cin >> opt;
        if(opt=="DONE") break;
        int x,y;
        cin >> x >> y;
        if(opt=="QUERY")
        {
            int res=0;
            while(ftop[x]!=ftop[y])
            {
                if(deg[x]<deg[y]) swap(x,y);
                res=max(tree.query(1,id[ftop[x]],id[x]),res);
                x=faa[ftop[x]];
//              cout << x << ' ' << y << '\n'; 
            }
            if(deg[x]<deg[y]) swap(x,y);
            res=max(tree.query(1,id[y]+1,id[x]),res);
            cout << res << '\n';
        }
        else tree.change(1,y,id[x+n]);
    }
    return 0;
}
/*
4
1 2 1
2 3 2
1 4 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
*/