题目链接：传送门
题目大意：给一棵无根树，树边有权值，有很多次操作，QUERY代表询问从 x 到 y 路径上的边的最大
权值，CHANGE代表改变按输入顺序第 x 条边的权值为 y。 对于每个QUERY，输出一个答案。
题目思路：树链剖分（第一次学树链，还有点云里雾里的）
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 10050 #define maxn 30010 typedef pair<int,int> PII; typedef long long LL; LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } int n,m,k,head[N],hcnt,rt; char str[11]; struct Node{ int to,nxt,v; }node[maxn]; struct Edge{ int x,y,v; }edge[maxn]; int seg[N<<2]; int siz[N]; ///当前节点保存的儿子数 int top[N]; ///当前节点所在链的顶端节点 int son[N]; ///保存重儿子 int dep[N]; ///当前节点深度 int fa[N]; ///当前节点的父亲 int id[N]; ///用来保存树中每个节点剖分后的新编号 int posi[N]; ///在线段树中的位置 int tid,pos; ///树链剖分 void dfs1(int u,int f,int deep){ ///找重边 dep[u]=deep; fa[u]=f; siz[u]=1; for(int i=head[u];~i;i=node[i].nxt){ int e=node[i].to; if(e==f)continue; dfs1(e,u,deep+1); siz[u]+=siz[e]; if(!son[u]||siz[son[u]]<siz[e]) son[u]=e; } } void dfs2(int u,int tp){ ///连重边成重链 top[u]=tp; id[u]=++tid; posi[id[u]]=u; if(!son[u])return; dfs2(son[u],tp); for(int i=head[u];~i;i=node[i].nxt){ int e=node[i].to; if(e!=son[u]&&e!=fa[u]) dfs2(e,e); } } ///线段树 void build(int rt,int l,int r){ seg[rt]=-inf; if(l==r) return; int mid=l+r>>1; build(lson); build(rson); seg[rt]=max(seg[rt<<1],seg[rt<<1|1]); } void add(int rt,int l,int r,int v){ if(l==r){ seg[rt]=v; return; } int mid=l+r>>1; if(pos<=mid)add(lson,v); else add(rson,v); seg[rt]=max(seg[rt<<1],seg[rt<<1|1]); } int query(int rt,int l,int r,int L,int R){ if(L<=l&&r<=R){return seg[rt];} int mid=l+r>>1; int temp=INT_MIN; if(L<=mid)temp=max(temp,query(lson,L,R)); if(R>mid) temp=max(temp,query(rson,L,R)); return temp; } void ini(){ mst(head,-1);hcnt=tid=0;mst(seg,0); mst(son,0);mst(siz,0); } void add(int x,int y,int v){ node[hcnt].to=y,node[hcnt].nxt=head[x],node[hcnt].v=v,head[x]=hcnt++; node[hcnt].to=x,node[hcnt].nxt=head[y],node[hcnt].v=v,head[y]=hcnt++; } int lca(int x,int y){ int ans=-inf; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); ans=max(ans,query(1,1,n,id[top[x]],id[x])); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); if(x!=y)ans=max(ans,query(1,1,n,id[x]+1,id[y])); return ans; } int main(){ //freopen("in.txt","r",stdin); int i,j,group,x,y,v,Case=0; group=read(); while(group--){ ini(); n=read(); for(i=1;i<n;++i){ scanf("%d%d%d",&x,&y,&v); edge[i].x=x,edge[i].y=y,edge[i].v=v; add(x,y,v); } dfs1(1,1,1); dfs2(1,1); build(1,1,n); for(i=1;i<n;i++){ if(dep[edge[i].x]<dep[edge[i].y]) swap(edge[i].x,edge[i].y); pos=id[edge[i].x]; add(1,1,n,edge[i].v); } while(scanf("%s",str)!=EOF){ if(str[0]=='D')break; x=read();y=read(); if(str[0]=='Q'){ printf("%d ",lca(x,y)); } else{ pos=id[edge[x].x]; add(1,1,n,y); } } printf(" "); } return 0; }