# SPOJ QTREE – Query on a tree （树链剖分）

## 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:

• CHANGE i ti : change the cost of the i-th edge to ti
• QUERY a b : ask for the maximum edge cost on the path from node a to node b

## Input

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

• In the first line there is an integer N (N <= 10000),
• In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),
• The next lines contain instructions “CHANGE i ti” or “QUERY a b”,
• The end of each test case is signified by the string “DONE”.

There is one blank line between successive tests.

## Output

For each “QUERY” operation, write one integer representing its result.

## Example

Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3


## AC 代码

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 10010;
struct Edge
{
int to;
int next;
} edge[maxn<<1];

int top[maxn];      //v所在重链的顶端节点
int fa[maxn];       //父亲节点
int deep[maxn];     //节点深度
int num[maxn];      //以v为根的子树节点数
int p[maxn];        //v与其父亲节点的连边在线段树中的位置
int fp[maxn];       //与p[]数组相反
int son[maxn];      //重儿子
int pos;
int e[maxn][3];

void init()
{
memset(son,-1,sizeof(son));
tot=0;
pos=0;
}

{
edge[tot].to=v;
}

void dfs1(int u,int pre,int d)         //第一遍dfs，求出 fa,deep,num,son (u为当前节点,pre为其父节点,d为深度)
{
deep[u]=d;
fa[u]=pre;
num[u]=1;
{
int v=edge[i].to;
if(v!=pre)
{
dfs1(v,u,d+1);
num[u]+=num[v];
if(son[u]==-1||num[v]>num[son[u]])  //寻找重儿子
son[u]=v;
}
}
}

void dfs2(int u,int sp)                 //第二遍dfs，求出 top,p
{
top[u]=sp;
p[u]=pos++;
fp[p[u]]=u;
if(son[u]!=-1)                      //如果当前点存在重儿子，继续延伸形成重链
dfs2(son[u],sp);
else return;
{
int v=edge[i].to;
if(v!=son[u]&&v!=fa[u])         //遍历所有轻儿子新建重链
dfs2(v,v);
}
}

int maxx[maxn<<2],dep=1;                //存储线段树各节点的值以及最底层元素个数

void build()           //一棵完美二叉树的初始化
{
while(dep<pos)
dep<<=1;
memset(maxx,0,sizeof(maxx));
}

void update(int o,int val)              //自底向上更新数据
{
o+=dep;
maxx[o]=val;
while(o>1)
{
o>>=1;
maxx[o]=max(maxx[o<<1],maxx[(o<<1)^1]);
}
}

int query(int a,int b,int k,int l,int r)    //查询[a,b]最大值，[l,r]为当前查询区间，k为当前所在节点
{
if(r<a||b<l)return 0;                   //如果当前查询区间与[a,b]交集为空，返回0
if(a<=l&&b>=r)return maxx[k];           //如果[a,b]包含[l,r]返回当前节点的值
else
{
int v1=query(a,b,k<<1,l,(l+r)>>1);  //左子树
int v2=query(a,b,(k<<1)^1,((l+r)>>1)+1,r);  //右子树
return max(v1,v2);
}
}

int find(int u,int v)
{
int f1=top[u],f2=top[v];
int tmp=0;
while(f1!=f2)
{
if(deep[f1]<deep[f2])
{
swap(f1,f2);
swap(u,v);
}
tmp=max(tmp,query(p[f1],p[u],1,0,dep-1));
u=fa[f1];
f1=top[u];
}
if(u==v)return tmp;
if(deep[u]>deep[v])swap(u,v);
return max(tmp,query(p[son[u]],p[v],1,0,dep-1));
}

int main()
{
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
init();
for(int i=0; i<n-1; i++)
{
for(int j=0; j<3; j++)
cin>>e[i][j];
}
dfs1(1,0,0);
dfs2(1,1);
build();
for(int i=0; i<n-1; i++)
{
if(deep[e[i][0]]>deep[e[i][1]])
swap(e[i][0],e[i][1]);
update(p[e[i][1]],e[i][2]);
}
char op[10];
while(cin>>op)
{
if(op[0]=='D')break;
int a,b;
cin>>a>>b;
if(op[0]=='C')
update(p[e[a-1][1]],b);
else if(op[0]=='Q')
cout<<find(a,b)<<endl;
}
}
return 0;
}