题目地址：SPOJ 375 树链剖分第一发! 果然是个貌似很高级的数据结构，其实就是把树的边从树形结构转化成了线性结构，，从而可以用线段树或树状数组之类的数据结构进行快速维护。从而将时间缩到n*log(2*n). 这题用的线段树维护的。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-3;const int MAXN=10000+10;Max[MAXN<<2], head[MAXN], cnt, n;int siz[MAXN], dep[MAXN], w[MAXN], top[MAXN], son[MAXN], fa[MAXN], tot;struct node{int u, v, w, next;}edge[MAXN<<1];void add(int u, int v, int w){edge[cnt].u=u;edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;}void init(){memset(head,-1,sizeof(head));cnt=0;memset(dep,0,sizeof(dep));memset(son,0,sizeof(son));memset(Max,0,sizeof(Max));tot=0;}void dfs1(int u, int p){siz[u]=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==p) continue ;dep[v]=dep[u]+1;dfs1(v,u);fa[v]=u;if(siz[v]>siz[son[u]]) son[u]=v;siz[u]+=siz[v];}}void dfs2(int u, int tp){w[u]=++tot; top[u]=tp;if(son[u]) dfs2(son[u],top[u]);for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v!=son[u]&&v!=fa[u])dfs2(v,v);}}struct Line_Tree{void PushUp(int rt){Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);}void Update(int p, int x, int l, int r, int rt){if(l==r){Max[rt]=x;return ;}int mid=l+r>>1;if(p<=mid) Update(p,x,lson);else Update(p,x,rson);PushUp(rt);}int Query(int ll, int rr, int l, int r, int rt){if(ll<=l&&rr>=r){return Max[rt];}int mid=l+r>>1, ans=0;if(ll<=mid) ans=max(Query(ll,rr,lson),ans);if(rr>mid) ans=max(ans,Query(ll,rr,rson));return ans;}}lt;int Query(int u, int v){int f1=top[u], f2=top[v], ans=0;while(f1!=f2){if(dep[f1]<dep[f2]){swap(u,v);swap(f1,f2);}ans=max(ans,lt.Query(w[f1],w[u],root));u=fa[f1];f1=top[u];}if(u==v) return ans;if(dep[u]<dep[v]) swap(u,v);return max(ans,lt.Query(w[son[v]],w[u],root));}int main(){int m, q, i, u, v, T, x, c;char s[10];scanf(“%d”,&T);while(T–){scanf(“%d”,&n);init();for(i=1;i<n;i++){scanf(“%d%d%d”,&u,&v,&c);add(u,v,c);add(v,u,c);}dfs1(1,-1);dfs2(1,1);for(i=0;i<cnt;i+=2){u=edge[i].u;v=edge[i].v;if(dep[u]<dep[v]) swap(u,v);lt.Update(w[u],edge[i].w,root);}while(scanf(“%s”,s)!=EOF&&s[0]!=’D’){if(s[0]==’C’){scanf(“%d%d”,&x,&c);u=edge[x-1<<1].u;v=edge[x-1<<1].v;if(dep[u]<dep[v]) swap(u,v);lt.Update(w[u],c,root);}else{scanf(“%d%d”,&u,&v);printf(“%d\n”,Query(u,v));}}}return 0;}
喜欢真实的人，要做真实的人，所以从来不会想要刻意模仿任何人。
