传送门 题解：树链剖分边权问题，属于本人万年不想碰系列，以前做过不少剖点权的，今天来填填坑。其实两种问题唯一不同的就是：边权问题需要把边权下放到儿子作为点权，然后在链剖向上跳的最后一步稍作修改即可。关于记录一条边以及它对应权值下放的点，本蒟蒻想了一个办法就是用map < pair < int ,int> ,int >，其中pair记录一条边起点终点，最后一个int即这条边权值下放的点编号。
经过肉眼在submission记录中的比较，这种写法略微牺牲时间但是代码长度较短。应该有更快的方法，不过对于链剖这种O(n*logn^2)的算法，在main()的外层循环加一个logn也几乎可以忽略不计（更何况map可是用红黑树实现的，快得吓人orzorz）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<map> using namespace std; #define root 1,1,n #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define pii pair<int ,int > const int MAXN=10004,INF=0x3f3f3f3f; int n; int head[MAXN],edge,fa[MAXN],dep[MAXN],son[MAXN],siz[MAXN]; int top[MAXN],tid[MAXN],rk[MAXN],num[MAXN],tim; map<pii ,int > mp; struct EDGE { int u,v,nxt,w; }e[MAXN<<1]; char ss[5]; inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline void adde(int u,int v,int w) { e[++edge].nxt=head[u],e[edge].u=u,e[edge].v=v,e[edge].w=w,head[u]=edge; e[++edge].nxt=head[v],e[edge].u=v,e[edge].v=u,e[edge].w=w,head[v]=edge; } /*------------DCP------------*/ void dfs1(int p,int father,int d) { dep[p]=d,fa[p]=father,siz[p]=1; for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (v^father) { mp[make_pair(e[i].u,e[i].v)]=v; mp[make_pair(e[i].v,e[i].u)]=v; dep[v]=dep[p]+1; num[v]=e[i].w; dfs1(v,p,d+1); siz[p]+=siz[v]; if (son[p]==-1||siz[son[p]]<siz[v]) son[p]=v; } } } void dfs2(int p,int tp) { top[p]=tp,tid[p]=++tim,rk[tim]=p; if (son[p]==-1) return ; dfs2(son[p],tp); for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (v^fa[p]&&v^son[p]) dfs2(v,v); } } /*------------SegTree------------*/ int mx[MAXN<<2]; inline void pushup(int rt) { mx[rt]=max(mx[rt<<1],mx[rt<<1|1]); } void build(int rt,int l,int r) { if (l==r) {mx[rt]=num[rk[l]];return ;} int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } void modify(int rt,int l,int r,int pos,int val) { if (l==r) {mx[rt]=val;return ;} int mid=(l+r)>>1; if (pos<=mid) modify(lson,pos,val); else modify(rson,pos,val); pushup(rt); } int query(int rt,int l,int r,int L,int R) { if (L<=l&&r<=R) return mx[rt]; int mid=(l+r)>>1,ret=-INF; if (L<=mid) ret=max(ret,query(lson,L,R)); if (mid<R) ret=max(ret,query(rson,L,R)); return ret; } int ask(int x,int y) { int ret=-INF; while (top[x]^top[y]) { if (dep[top[x]]<dep[top[y]]) x^=y^=x^=y; ret=max(ret,query(root,tid[top[x]],tid[x])); x=fa[top[x]]; } if (x==y) return ret; if (dep[x]>dep[y]) x^=y^=x^=y; ret=max(ret,query(root,tid[son[x]],tid[y]));//son!!! return ret; } int main() { // freopen("spoj qot.in","r",stdin); int kase=read(); while (kase--) { edge=tim=0; memset(head,-1,sizeof(head)); memset(son,-1,sizeof(son)); n=read(); for (int i=1;i<n;++i) { int u=read(),v=read(),w=read(); adde(u,v,w); } dfs1(1,0,0); num[1]=-INF,dfs2(1,1); build(root); while (scanf("%s",ss)&&ss[1]^'O') { if (ss[0]=='Q') { int x=read(),y=read(); printf("%d\n",ask(x,y)); } else { int eg=read()<<1,val=read(); int u=e[eg].u,v=e[eg].v; int pos=mp[make_pair(u,v)]; modify(root,tid[pos],val); } } } return 0; }