有 n 个节点，n-1 条边，每一条边都有一个边权，现在求 在 [a,b] 节点上花费最大的边权，及将 第 i 条边的权值变为 权值c
这个题和普通的树链剖分不同，由于每个节点只有一个父节点，但是有多个子节点，所以以子节点看作边求解（也可以将节点想象成一个区间，大概）
和之前不同的是，再更新边权时，要找到深度最大的那个节点
在查询边权时，由于第一次 deep 较大的 x 跳到了其父节点的位置上，那么下一次应该是从 fa[x]+1 上开始跳
还要注意的是，有 t 组测试样例，重儿子啥的别忘初始化
调个板子还这么费劲，不愧是我（doge）
const int N=1e4+5; int n,m,t; int i,j,k; int a[N]; vector<Pair> G[N]; struct Node { int l, r; int maxx; }node[N<<2]; void push_up(int id) { //node[id].sum=node[id<<1].sum+node[id<<1|1].sum; node[id].maxx=max(node[id<<1].maxx,node[id<<1|1].maxx); } int sz[N],son[N],fa[N],dep[N]; void dfs1(int u,int f) //子节点 u，父节点 f { sz[u]=1; fa[u]=f; dep[u]=dep[f]+1; son[u]=0; int len=G[u].size(); for(int i=0;i<len;i++){ int v=G[u][i].fr; if(v==f) continue; a[v]=G[u][i].sc; dfs1(v,u); sz[u]+=sz[v]; if(sz[v]>sz[ son[u] ]) son[u]=v; } } int top[N],id[N],tree[N],tot=0; void dfs2(int u,int f) { top[u]=f; id[u]=++tot; tree[ tot ]=u; //tree[ id[u] ]=u; if(!son[u]) return ; //叶子节点 dfs2(son[u],f); int len=G[u].size(); for(int i=0;i<len;i++){ int v=G[u][i].fr; if(v==son[u] || v==fa[u]) continue; dfs2(v,v); } } void build(int l,int r,int id) { node[id].l=l,node[id].r=r; node[id].maxx=0; if(l==r){ node[id].maxx=a[ tree[l] ]; } else{ int mid=l+r>>1; build(l,mid,id<<1); build(mid+1,r,id<<1|1); push_up(id); } } int query(int l,int r,int id) { int L=node[id].l,R=node[id].r; if(L>=l && r>=R){ return node[id].maxx; } else{ int ans=-inf; int mid=L+R>>1; if(mid>=l) ans=max(query(l,r,id<<1),ans); if(r>=mid+1) ans=max(query(l,r,id<<1|1),ans); return ans; } } void update(int id,int pos,int val) { int L=node[id].l; int R=node[id].r; if(L==R){ node[id].maxx=val; return ; } else{ int mid=L+R>>1; if(mid>=pos) update(id<<1,pos,val); else update(id<<1|1,pos,val); push_up(id); } } #define nx top[x] #define ny top[y] int ask(int x,int y) { int ans=-inf; while(nx!=ny){ if(dep[nx]<dep[ny]) swap(x,y); ans = max(query(id[nx],id[x],1),ans); x=fa[nx]; } if(dep[x]>dep[y]) swap(x,y); if(x!=y) ans=max(query(id[x]+1,id[y],1),ans); return ans; } void init() { for(int i=0;i<N;i++) G[i].clear(); tot=0; } struct Edge { int u,v,w; }E[N]; int main() { //IOS; rush(){ sd(n); init(); int x,y,k; for(i=1;i<=n-1;i++){ sddd(x,y,k); G[x].pb( mp(y,k) ); G[y].pb( mp(x,k) ); E[i]={x,y,k}; } dfs1(1,0); dfs2(1,1); build(1,n,1); char s[10]; while(true){ ss(s); if(s[0]=='Q'){ sdd(x,y); pd( ask(x,y) ); } else if(s[0]=='C'){ sdd(x,y); int u=dep[ E[x].u ]>dep[ E[x].v ]? E[x].u : E[x].v; update(1,id[u],y); } else if(s[0]=='D') break; } } //PAUSE; return 0; }
