树链剖分 80pts 关爱弱智儿童，下饭代码有助开胃

#include <bits/stdc++.h>
using namespace std;

long long T, n, a[300005], x, y, z,seg[300005][2],sz[300005], dep[300005], son[300005],vson[300005],top[300005], fa[300005],dfn[300005],cnt;
struct node
{
    long long to,w;
};
struct nde
{
    long long mx,l,r;
}t[300005];
vector<node> v[300005];
char c[10];
inline long long read() {
    char c = getchar();
    long long f = 1;
    long long sum = 0;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') {
        f = -1;
        c = getchar();
    }
    do {
        sum = (sum << 3) + (sum << 1) + c - '0';
        c = getchar();
    } while (c >= '0' && c <= '9');
    return sum * f;
}
void dfs1(long long x) {
    sz[x] = 1, dep[x] = dep[fa[x]] + 1;
    for (auto i : v[x]) {
        if (i.to == fa[x])
            continue;
        fa[i.to] = x;
        dfs1(i.to);
        sz[x] += sz[i.to];
        if (sz[son[x]] < sz[i.to])
            son[x] = i.to,vson[x]=i.w;
    }
}
void dfs2(long long x, long long t,long long w) {
    top[x] = t,dfn[x]=++cnt,a[cnt]=w;
    if (son[x])
        dfs2(son[x], t,vson[x]);
    for (auto i : v[x]) {
        if (i.to == fa[x] || i.to == son[x])
            continue;
        dfs2(i.to, i.to,i.w);
    }
}
void build(long long pos,long long l,long long r)
{

    t[pos].l=l;
    t[pos].r=r;
    if(l==r)
    {        
        t[pos].mx=a[l];
        return;
    }
    long long mid=(l+r)/2;
    build(pos*2,l,mid);
    build(pos*2+1,mid+1,r);
    t[pos].mx=max(t[pos*2].mx,t[pos*2+1].mx);
}
void change(long long pos,long long l,long long k)
{
    if(l<t[pos].l||t[pos].r<l)return;  
    if(t[pos].l==t[pos].r)
    {
        if(t[pos].l==l)t[pos].mx=k;
        return;
    } 
    change(pos*2,l,k),change(pos*2+1,l,k);   
    t[pos].mx=max(t[pos*2].mx,t[pos*2+1].mx);
}
long long querymx(long long pos,long long l,long long r)
{
    if(r<t[pos].l||t[pos].r<l)return 0;
    if(l<=t[pos].l&&t[pos].r<=r)return t[pos].mx;
    return max(querymx(pos*2,l,r),querymx(pos*2+1,l,r));   
}
long long query(long long x,long long y)
{
    long long tx=top[x],ty=top[y],ans=0;
    while (tx!=ty) {
        if(dep[tx]<dep[ty])swap(tx,ty),swap(x,y);
        ans=max(querymx(1,dfn[tx],dfn[x]),ans);
        x=fa[tx],tx=top[x];

    }
    if (dep[x] > dep[y])
        swap(x, y);
    ans=max(ans,querymx(1,dfn[son[x]],dfn[y]));
    return ans;
}
int main() {
    T=1;
    while(T--)
    {
        cnt=0;
        memset(v,0,sizeof(v));
        memset(t,0,sizeof(t));
        memset(dep,0,sizeof(dep));
        memset(top,0,sizeof(top));
        memset(a,0,sizeof(a));
        memset(fa,0,sizeof(fa));
        memset(dfn,0,sizeof(dfn));
        memset(son,0,sizeof(son));
        memset(vson,0,sizeof(vson));
        memset(seg,0,sizeof(seg));
        memset(sz,0,sizeof(sz));
        n=read();
        for (int i = 1; i <= n - 1; i++) {
            scanf("%lld%lld%lld", &x, &y,&z);
            seg[i][0]=x,seg[i][1]=y;
            v[x].push_back({y,z});
            v[y].push_back({x,z});
        }
        dfs1(1);
        dfs2(1,1,0); 
        for(int i=1;i<=n-1;i++)
        {
            if(dep[seg[i][0]]>dep[seg[i][1]])
            {
                swap(seg[i][0],seg[i][1]);
            }
        } 
        build(1,1,n);
        while(1)    
        {
            scanf("%s",c);
            if(c[0]=='D')break;
            scanf("%lld%lld",&x,&y);
            if(c[0]=='Q')
            {
                printf("%lld\n",query(x,y));
            }
            else 
            {
                change(1,dfn[seg[x][1]],y);
            }
        }  
    }

}