题目连接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28982#problem/I
题意：一棵包含N 个结点的树，每条边都有一个权值，要求模拟两种操作：
(1)改变某条边的权值。
(2)询问U,V 之间的路径中权值最大的边。
树链剖分裸题，入门资料：http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 10007 #define inf 0x3f3f3f3f #define N 10010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; struct edge { int to,next; edge(){} edge(int to,int next):to(to),next(next){} }e[N<<1]; int head[N<<1],tot; int top[N];//top[v]表示v所在的重链的顶端节点 int fa[N];//父亲节点 int dep[N];//深度 int sz[N];//si[v]表示以v为根节点的子树的节点数 int son[N];//重儿子 int p[N];//p[v]表示v与其父亲节点的连边在线段树中的位置 int fp[N];//与p数组相反 int pos;//所有链构成的线段树总长度 int mx[N<<2],E[N][3]; void addedge(int u,int v) { e[tot]=edge(v,head[u]); head[u]=tot++; } void init() { tot=0;FILL(head,-1); pos=0;FILL(son,-1); } void dfs(int u,int f,int d) { sz[u]=1;dep[u]=d;fa[u]=f; for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(v==f)continue; dfs(v,u,d+1); sz[u]+=sz[v]; if(son[u]==-1||sz[son[u]]<sz[v])son[u]=v; } } void getpos(int u,int sp) { top[u]=sp; p[u]=++pos; fp[pos]=u; if(son[u]==-1)return; getpos(son[u],sp); for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(v!=son[u]&&v!=fa[u]) { getpos(v,v); } } } int Pushup(int rt) { mx[rt]=max(mx[rt<<1],mx[rt<<1|1]); } void update(int id,int c,int l,int r,int rt) { if(l==r) { mx[rt]=c; return; } int m=(l+r)>>1; if(id<=m)update(id,c,lson); else update(id,c,rson); Pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return mx[rt]; int m=(l+r)>>1; int res=-inf; if(L<=m)res=max(res,query(L,R,lson)); if(m<R)res=max(res,query(L,R,rson)); return res; } int lca(int u,int v) { int fu=top[u],fv=top[v]; int res=-inf; while(fu!=fv) { if(dep[fu]<dep[fv]) { swap(fu,fv);swap(u,v); } res=max(res,query(p[fu],p[u],1,pos,1)); u=fa[fu];fu=top[u]; } if(u==v)return res; if(dep[u]>dep[v])swap(u,v); return max(res,query(p[son[u]],p[v],1,pos,1)); } int main() { int T,n,u,v; scanf("%d",&T); while(T--) { init(); scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d%d",&E[i][0],&E[i][1],&E[i][2]); addedge(E[i][0],E[i][1]); addedge(E[i][1],E[i][0]); } dfs(1,0,0); getpos(1,1); for(int i=1;i<n;i++) { if(dep[E[i][0]]>dep[E[i][1]]) swap(E[i][0],E[i][1]); update(p[E[i][1]],E[i][2],1,pos,1); } char op[10]; while(1) { scanf("%s",op); if(op[0]=='D')break; scanf("%d%d",&u,&v); if(op[0]=='Q') printf("%d ",lca(u,v)); else update(p[E[u][1]],v,1,pos,1); } } }