树链剖分的第一题，易懂，注意这里是边。
#include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 99999999 #define ll __int64 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN = 10010; struct node { int to; int v; int next; }edge[MAXN*3]; int pre[MAXN],ind,top[MAXN],fa[MAXN],son[MAXN],w[MAXN],deq[MAXN],siz[MAXN],fn; int tree[MAXN<<2],val[MAXN][3],n; void add(int x,int y,int z) { edge[ind].to = y; edge[ind].v = z; edge[ind].next = pre[x]; pre[x] = ind++; } //第一次搜索找出siz[],son[],deq[],fa[] void dfs1(int rt,int pa,int d) { deq[rt] = d; son[rt] = 0; fa[rt] = pa; siz[rt] = 1; int i; for(i=pre[rt]; i!=-1; i=edge[i].next){ int t = edge[i].to; if(t != fa[rt]){ dfs1(t,rt,d+1); siz[rt] += siz[t]; if(siz[son[rt]] < siz[t]){//如果父节点的son[rt]的iz[]小于子节点的siz[]更新son[] son[rt] = t; } } } } //第二次搜索找到w[],top[] void dfs2(int rt,int tp) { top[rt] = tp; w[rt] = ++fn; if(son[rt] != 0) dfs2(son[rt],tp);//如果当前父节点纯在son 那么为了让链在线段树中连续 先对son[]进行搜索，并且重边顶端的点相同。 for(int i=pre[rt]; i!=-1; i=edge[i].next){ int t = edge[i].to; if(t != fa[rt] && son[rt] != t){ dfs2(t,t); } } } void updata(int p,int v,int l,int r,int rt) { if(l == r){ tree[rt] = v; return ; } int m = (l+r)/2; if(m >= p){ updata(p,v,lson); } else { updata(p,v,rson); } tree[rt] = max(tree[rt<<1],tree[rt<<1|1]); } int query(int L,int R,int l,int r,int rt) { if(L<=l && r<=R){ return tree[rt]; } int m = (l+r)/2; int ans = 0; if(m >= L){ ans = max(ans,query(L,R,lson)); } if(m < R){ ans = max(ans,query(L,R,rson)); } return ans; } int lca(int x,int y) { int f1,f2; int ans = 0; while(top[x] != top[y]) { if(deq[top[x]] < deq[top[y]]){ swap(x,y); } ans = max(ans,query(w[top[x]],w[x],1,fn,1)); x = fa[top[x]]; } if(x == y) return ans; if(deq[x] < deq[y]){ swap(x,y); } return max(ans,query(w[son[y]],w[x],1,fn,1)) ; } int main() { int i,j,t; scanf("%d",&t); while(t--) { scanf("%d",&n); ind = 1; memset(pre,-1,sizeof(pre)); for(i=1; i<n; i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); val[i][0] = x; val[i][1] = y; val[i][2] = z; add(x,y,z); add(y,x,z); } memset(tree,0,sizeof(tree)); dfs1(1,1,1); fn = 0; dfs2(1,1); for(i=1; i<n; i++){ if(deq[val[i][0]] > deq[val[i][1]]){ swap(val[i][0],val[i][1]); } updata(w[val[i][1]],val[i][2],1,fn,1); } char s[15]; while(1) { scanf("%s",s); if(s[0] == 'D') break; if(s[0] == 'C'){ int x,y; scanf("%d%d",&x,&y); updata(w[val[x][1]],y,1,fn,1); } else { int x,y; scanf("%d%d",&x,&y); printf("%d ",lca(x,y)); } } } }