本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.
We will ask you to perfrom some instructions of the following form:
The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.
For each test case:
There is one blank line between successive tests.
For each "QUERY" operation, write one integer representing its result.
Input: 1 3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE Output: 1 3
正解：树链剖分
解题报告：
链剖裸题，注意清空数组。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
#define lc root<<1
#define rc root<<1|1
typedef long long LL;
const int MAXN = 20011;
const int MAXM = 40011;
const int inf = (1<<30);
int n,ecnt,first[MAXN],to[MAXM],next[MAXM],w[MAXM],father[MAXN],quan[MAXN],quanv[MAXN];
int deep[MAXN],id[MAXN],pre[MAXN],son[MAXN],size[MAXN],top[MAXN],match[MAXN],ans,ql,qr,CC;
char ch[12];
struct node{ int maxl; }a[MAXN*3];
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline void dfs(int x,int fa){
size[x]=1;
for(int i=first[x];i;i=next[i]) {
int v=to[i]; if(v==fa) continue;
father[v]=x; deep[v]=deep[x]+1; quanv[v]=(i+1)>>1;
quan[v]=w[i]; match[(i+1)>>1]=v;
dfs(v,x); size[x]+=size[v];
if(size[v]>=size[son[x]]) son[x]=v;
}
}
inline void dfs2(int x,int fa){
id[x]=++ecnt; pre[ecnt]=x;
if(son[x]) top[son[x]]=top[x],dfs2(son[x],x);
for(int i=first[x];i;i=next[i]) {
int v=to[i]; if(v==fa || v==son[x]) continue;
top[v]=v; dfs2(v,x);
}
}
inline void build(int root,int l,int r){
if(l==r) { a[root].maxl=quan[pre[l]]; return ; }
int mid=(l+r)>>1; build(lc,l,mid); build(rc,mid+1,r);
a[root].maxl=max(a[lc].maxl,a[rc].maxl);
}
inline void query(int root,int l,int r){
if(ql<=l && r<=qr) { ans=max(ans,a[root].maxl); return ; }
int mid=(l+r)>>1; if(ql<=mid) query(lc,l,mid); if(qr>mid) query(rc,mid+1,r);
}
inline void lca(int x,int y){
ans=-inf; int f1=top[x],f2=top[y];
while(f1!=f2) {
if(deep[f1]<deep[f2]) swap(f1,f2),swap(x,y);
ql=id[f1]; qr=id[x]; query(1,1,n);
x=father[f1]; f1=top[x];
}
if(deep[x]<deep[y]) swap(x,y);
ql=id[son[y]]; qr=id[x];
if(ql<=qr) query(1,1,n);
printf("%d\n",ans);
}
inline void update(int root,int l,int r){
if(l==r) { a[root].maxl=CC; return ; }
int mid=(l+r)>>1;
if(ql<=mid) update(lc,l,mid); else update(rc,mid+1,r);
a[root].maxl=max(a[lc].maxl,a[rc].maxl);
}
inline void work(){
int T=getint(); int x,y,z;
while(T--) {
n=getint(); ecnt=0; memset(first,0,sizeof(first));
memset(son,0,sizeof(son));
for(int i=1;i<n;i++) {
x=getint(); y=getint(); z=getint();
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z;
next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x; w[ecnt]=z;
}
deep[1]=1; dfs(1,0);
ecnt=0; top[1]=1; dfs2(1,0);
build(1,1,n);
while(1) {
scanf("%s",ch); if(ch[0]==‘D‘) break;
if(ch[0]==‘Q‘) {
x=getint(); y=getint();
lca(x,y);
}
else {
x=getint(); y=getint(); CC=y;
z=match[x];//边对应的连接的儿子节点
quan[z]=y; ql=id[z]; update(1,1,n);
}
}
}
}
int main()
{
work();
return 0;
}
SPOJ375 QTREE - Query on a tree
原文：http://www.cnblogs.com/ljh2000-jump/p/6367163.html