题目传送门：[SPOJ - QTREE] Query on a tree
题目大意：
存在一个树，树上有n个节点和n-1条边，对这棵树进行以下两种操作
CHANGE i ti ：将树的第i条边的权值改为ti
QUERY a b ：查询a->b路径中权值最大的边的值
分析：
边权树链剖分裸题，CHANGE操作是更改第i条边，因此边用结构体数组将其保存，用边
的两个点中深度较大的点记录边的权值，更改时更改该点，为了方便操作，两次dfs之后
重新遍历保存边的结构体数组，将深度较大的边存在E[i].u中。更新时更新该点即可。
注意：因为用深度较大的点记录该边的权值，x点所记录的权值是边x->fa[x]的权值,因此当x和y在
同一条重链时：对x->y路径进行操作时，其实是对son[x]->y的点所记录的权值进行操作.
(这里假设：deep[x]<deep[y])
线段树维护区间最大值，查询为区间查询
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 const int MAX=10000; const int INF=1<<29; int head[MAX],cnt; int fa[MAX],deep[MAX],son[MAX],size[MAX],top[MAX],id[MAX],rk[MAX],tot; int t,n,x,y,a[MAX]; int tree[MAX<<2]; char op[10]; struct Edge{ int next,to; }edge[MAX*2]; void add(int u,int v) { edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } struct E{ //记录边信息 int u,v,w; }e[MAX]; void dfs1(int u,int f,int d) { fa[u]=f; deep[u]=d; size[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=fa[u]) { dfs1(v,u,d+1); size[u]+=size[v]; if(son[u]==-1||size[v]>size[son[u]]) son[u]=v; } } } void dfstop(int u,int t) { top[u]=t; id[u]=tot++; rk[id[u]]=u; if(son[u]==-1)return; dfstop(son[u],t); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=son[u]&&v!=fa[u]) dfstop(v,v); } } void PushUp(int rt) //维护区间最大值 { tree[rt]=max(tree[rt<<1],tree[rt<<1|1]); } void Build(int l,int r,int rt) { if(l==r) { tree[rt]=a[rk[l]]; return; } int m=l+r>>1; Build(ls),Build(rs); PushUp(rt); } void Update(int pos,int val,int l,int r,int rt)//单点更新 { if(l==r) { tree[rt]=val; return; } int m=l+r>>1; if(pos<=m)Update(pos,val,ls); else Update(pos,val,rs); PushUp(rt); } int Query(int L,int R,int l,int r,int rt)//区间查询 { if(L<=l&&r<=R) return tree[rt]; int ans=-INF; int m=l+r>>1; if(L<=m)ans=max(ans,Query(L,R,ls)); if(R>m)ans=max(ans,Query(L,R,rs)); return ans; } int solve(int x,int y)//查询x->y路径中边权最大的值 { int ans=-INF; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); ans=max(ans,Query(id[top[x]],id[x],1,tot,1)); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); ans=max(ans,Query(id[son[x]],id[y],1,tot,1));//x->y路径的权值记录在son[x]->y之间，x点记录的是x到其父亲节点的权值 return ans; } void init() { memset(head,-1,sizeof(head));cnt=0; memset(son,-1,sizeof(son));tot=1; memset(tree,0,sizeof(tree)); memset(a,0,sizeof(a)); } int main() { scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); add(e[i].u,e[i].v),add(e[i].v,e[i].u); } dfs1(1,-1,0),dfstop(1,1); for(int i=1;i<n;i++) { if(deep[e[i].u]<deep[e[i].v]) //将边两边的点深度较大的点记录在u中 swap(e[i].u,e[i].v); a[e[i].u]=e[i].w; //深度较大的点保存该边的权值 } Build(1,tot,1); while(scanf("%s",op)) { if(op[0]=='D')break; if(op[0]=='C') { scanf("%d%d",&x,&y); Update(id[e[x].u],y,1,tot,1); //更新深度较大的点的权值即更新该边的权值 } if(op[0]=='Q') { scanf("%d%d",&x,&y); printf("%d\n",solve(x,y)); } } } return 0; }