题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28982#problem/I
给你一棵有边权的树，有两个操作：一个操作是输出l到r点之间的最大的边权，另一个操作是修改某条边的权值。
这题是树链剖分的简单模版题，代码如下：
//修改单边权
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e4 + ;
struct data {
int next , to , cost;
}edge[MAXN << ];
int head[MAXN] , top[MAXN] , id[MAXN] , par[MAXN] , dep[MAXN] , size[MAXN] , son[MAXN];
int cnt , tot , v[MAXN] , u[MAXN] , cost[MAXN]; void init() {
cnt = tot = ;
memset(head , - , sizeof(head));
} inline void add(int u , int v , int cost) {
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].cost = cost;
head[u] = cnt++;
} void dfs_1(int u , int p , int d) {
dep[u] = d , par[u] = p , size[u] = , son[u] = u;
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p)
continue;
dfs_1(v , u , d + );
if(size[son[u]] < size[v])
son[u] = v;
size[u] += size[v];
}
} void dfs_2(int u , int p , int t) {
top[u] = t , id[u] = ++tot;
if(son[u] != u)
dfs_2(son[u] , u , t);
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p || v == son[u])
continue;
dfs_2(v , u , v);
}
} struct segtree {
int l , r , Max;
}T[MAXN << ]; void build(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r;
if(l == r)
return ;
build(p << , l , mid);
build((p << )| , mid + , r);
} void updata(int p , int pos , int num) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == T[p].r) {
T[p].Max = num;
return ;
}
if(pos <= mid)
updata(p << , pos , num);
else
updata((p << )| , pos , num);
T[p].Max = max(T[p << ].Max , T[(p << )|].Max);
} int query(int p , int l , int r) {
int mid = (T[p].l + T[p].r) >> ;
if(l == T[p].l && T[p].r == r)
return T[p].Max;
if(r <= mid)
return query(p << , l , r);
else if(l > mid)
return query((p << )| , l , r);
else
return max(query(p << , l , mid) , query((p << )| , mid + , r));
} int Find(int l , int r) {
int pl = top[l] , pr = top[r] , Max = ;
while(pl != pr) {
if(dep[pl] > dep[pr]) {
Max = max(Max , query( , id[pl] , id[l]));
l = par[pl];
pl = top[l];
}
else {
Max = max(Max , query( , id[pr] , id[r]));
r = par[pr];
pr = top[r];
}
}
if(r == l)
return Max;
else if(dep[r] > dep[l])
return max(Max , query( , id[son[l]] , id[r]));
else
return max(Max , query( , id[son[r]] , id[l]));
} int main()
{
int t , n , l , r;
scanf("%d" , &t);
while(t--) {
scanf("%d" , &n);
init();
for(int i = ; i < n ; ++i) {
scanf("%d %d %d" , u + i , v + i , cost + i);
add(u[i] , v[i] , cost[i]);
add(v[i] , u[i] , cost[i]);
}
dfs_1( , , );
dfs_2( , , );
build( , , tot);
for(int i = ; i < n ; ++i) {
if(dep[u[i]] > dep[v[i]])
swap(u[i] , v[i]);
updata( , id[v[i]] , cost[i]);
}
char q[];
while(scanf("%s" , q) && q[] != 'D') {
scanf("%d %d" , &l , &r);
if(q[] == 'C') {
updata( , id[v[l]] , r);
}
else {
printf("%d\n" , Find(l , r));
}
}
}
return ;
}