【题目描述】
一天机房的夜晚，无数人在MC里奋斗着。。。
大家都知道矿产对于MC来说是多么的重要，但由于矿越挖越少，勇士们不得不跑到更远的地方挖矿，但这样路途上就会花费相当大的时间，导致挖矿效率底下。
cjj提议修一条铁路，大家一致同意。
大家都被CH分配了一些任务：
zjmfrank2012负责绘制出一个矿道地图，这个地图包括家（当然这也是一个矿，毕竟不把家掏空我们是不会走的），和无数个矿，所以大家应该可以想出这是一个无向无环图，也就是一棵树。
Digital_T和cstdio负责铺铁路。。所以这里没他们什么事，两位可以劳作去了。
这个时候song526210932和RMB突然发现有的矿道会刷怪，并且怪的数量会发生变化。作为采矿主力，他们想知道从一个矿到另一个矿的路上哪一段会最困难。。。（困难值用zjm的死亡次数表示）。
【输入格式】
输入文件的第一行有一个整数N，代表矿的数量。矿的编号是1到N。
接下来N-1行每行有三个整数a,b,c，代表第i号矿和第j号矿之间有一条路，在初始时这条路的困难值为c。
接下来有若干行，每行是“CHANGE i ti”或者“QUERY a b”，前者代表把第i条路（路按所给顺序从1到M编号）的困难值修改为ti，后者代表查询a到b所经过的道路中的最大困难值。
输入数据以一行“DONE”结束。
【输出格式】
对每个“QUERY”操作，输出一行一个正整数，即最大困难值。
【分析】
实在是让人无语的背景改变，顺便膜拜一下梦迪神牛Orzzzzzzzz。
最基本的树链剖分。
#include <cstring>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
const int maxn=+;
using namespace std;
struct Edge
{
int to;//所指向的
int num;//记录边的编号
};
int d[maxn][],edge=,n,root;//用来记录边的属性
int siz[maxn],son[maxn];//子树大小和重儿子
int fa[maxn],dep[maxn],z;//父亲和深度
int w[maxn],top[maxn],tree[maxn];
char str[];
vector<Edge>map[maxn]; inline void init();
inline void work();
inline void dfs(int u);//第一次DFS
inline void addEdge(int u,int v);//加边
inline void make_tree(int u,int tp);//第二次DFS
inline void update(int root,int l,int r,int num,int c);//c是变更值
inline int read();//读入函数
inline int find(int a,int b);
inline int maxi(int root,int l,int r,int l1,int l2); inline void addEdge(int u,int v)
{
edge++;
map[u].push_back((Edge){v,edge});
}
inline void dfs(int u)//第一次dfs
{
int i;
siz[u]=;
son[u]=;
for (i=;i<map[u].size();i++)
{
int v=map[u][i].to;
if (v!=fa[u])
{
fa[v]=u;//更新父亲
dep[v]=dep[u]+;//更新深度
dfs(v);
if (siz[v]>siz[son[u]]) son[u]=v;
siz[u]+=siz[v];
}
}
}
//建树操作
inline void make_tree(int u,int tp)
{
int i;
w[u]=++z;
top[u]=tp;
if (son[u]!=) make_tree(son[u],top[u]);//优先走重儿子
for (i=;i<map[u].size();i++)
{
int v=map[u][i].to;
if (v!=son[u] && v!=fa[u])
make_tree(v,v);
}
}
//修改操作
inline void update(int root,int l,int r,int num,int c)
{
if (num>r || num<l) return;
if (l==r) {tree[root]=c;return;}
int mid=(l+r)/;
//递归修改
update(root*,l,mid,num,c);
update(root*+,mid+,r,num,c);
tree[root]=max(tree[root*],tree[root*+]);
}
inline void init()
{
int i;
scanf("%d",&n);
root=(+n)/;//随机根
fa[root]=z=dep[root]=edge=;
memset(d,,sizeof(d));
memset(tree,,sizeof(tree));
for (i=;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
d[i][]=u;d[i][]=v;d[i][]=w;
addEdge(u,v);//加无向边
addEdge(v,u);
}
dfs(root);//第一次
make_tree(root,root);
for (i=;i<n;i++)
{
if (dep[d[i][]]>dep[d[i][]]) swap(d[i][],d[i][]);//交换
update(,,z,w[d[i][]],d[i][]);//开始加边
}
return;
}
inline int read()
{
scanf("%s",str);
if (str[]=='D')
return ;
//printf("%s\n",str);
return ;
}
inline int maxi(int root,int l,int r,int l1,int r1)
{
if (l1>r || r1<l) return ;//边界条件
if (l1<=l && r<=r1) return tree[root];
int mid=(l+r)/;
return max(maxi(root*,l,mid,l1,r1),maxi(root*+,mid+,r,l1,r1));
}
//进行从a到b的询问
inline int find(int a,int b)
{
int f1=top[a],f2=top[b],temp=;
while (f1!=f2)//LCA
{
if (dep[f1]<dep[f2])//统一深度
{
swap(f1,f2);
swap(a,b);
}
temp=max(temp,maxi(,,z,w[f1],w[a]));
a=fa[f1];f1=top[a];//向上传递
}
if (a==b) return temp;
if (dep[a]>dep[b]) swap(a,b);
return max(temp,maxi(,,z,w[son[a]],w[b]));
}
inline void work()
{
int a,b;
while (read())
{
scanf("%d%d",&a,&b);
if (str[]=='Q') printf("%d\n",find(a,b));
else update(,,z,w[d[a][]],b);
}
return;
}
int main()
{
//文件操作
freopen("qtree.in","r",stdin);
freopen("qtree.out","w",stdout);
init();//初始化
work();
return ;
}