Brief description :
動態維護樹中兩點之間路徑上邊權的最大值。
Tags: Classical
Analysis :
經典問題.. . 樹鏈剖分 300- 行，3.10+ s
動態樹 150- 行。。。 2.90+ s…
（目前 Yang Zhe 作業里的 全局平衡二叉樹 還不知道怎麼實現。>_<。）
樹鏈剖分（。。過去的寫法。。。3s+-。。。
上面是我最開始時的寫法。。寫的非常小心謹慎。。。上來就分別對結點、邊、路徑各定義了一組結構體。。。（Vertex, Edge, Path … 然後全程指針指來指去。。
點和邊各有一個 host 指針。。（點寄宿在邊上。。邊寄宿在重路徑上。。。
。。路徑的本體是一棵線段樹，（。。為了刷榜還特地寫成了自下向上維護的形式。（因為有剪枝。。。。
。然後記錄其最高點的 Vertex 的指針。。（。head。。（。。跳鏈和詢問的時候計算 offset 都要用到。。。
。。
樹鏈剖分（。。。現在的寫法。。3s+-。。。
.. 只保留的 path 這一個結構體。。直接記錄每個點所在的路徑。。。
/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)
#define DO(n) while(n--)
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define Rush int T____; RD(T____); DO(T____)
#pragma comment(linker, "/STACK:36777216")
#pragma GCC optimize ("O2")
template<class T> inline void RD(T &);
template<class T> inline void OT(const T &);
template<class T> inline T& _RD(T &x){ RD(x); return x;}
inline void RS(char *s){scanf("%s", s);}
template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void CLR(T &A){A.clear();}
template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}
inline int _1(int i){return 1<<i;}
template<class T> inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}
template<class T> inline void OT(const T &x){printf("%d\n", x);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
/* .................................................................................................................................. */
const int N = 10001, M = 2 * N;
int l[N], r[N], p[N], w0[N], w1[N]; bool rt[N];
// Link-cut tree
int hd[N], nxt[M], a[M], b[M], w[M], h[M/2];
// Adjacent list
int n, ans;
#define lx l[x]
#define rx r[x]
inline void Update(int x){
w1[x] = max(w1[lx], w1[rx], w0[x]);
}
inline void Set(int l[], int y, int x){
l[y] = x, p[x] = y;
}
inline void Rotate(int x){
int y = p[x], z = p[y];
if (!rt[y]) Set(y == l[z] ? l : r, z, x);
else p[x] = z;
if (x == l[y]) Set(l, y, rx), Set(r, x, y);
else Set(r, y, lx), Set(l, x, y);
if (rt[y]) rt[y] = false, rt[x] = true; //rt[0] = true;
Update(y); //Update(x);
}
inline void Splay(int x){
while (!rt[x]) Rotate(x);
}
void Access(int x){
int y = 0; do{
Splay(x);
rt[rx] = true, rt[rx = y] = false, Update(x);
x = p[y = x];
} while (x);
}
// public:
void Query(int x, int y){
Access(y), y = 0; do{
Splay(x); if (!p[x]) OT(max(w1[rx], w1[y]));
rt[rx] = true, rt[rx = y] = false, Update(x);
x = p[y = x];
} while (x);
}
void Modify(int x, int val){
Splay(x), w0[x] = val;
}
#define v b[i]
#define w w[i]
inline void dfs(int u = 1){
for(int i=hd[u];i;i=nxt[i]) if (!p[v]){
p[v] = u, w0[v] = w, dfs(h[i>>1] = v);
}
}
#undef x
#undef w
int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//ios::sync_with_stdio(false);
Rush{
// Initializing Phase ...
FOR_C(i, 2, _RD(n) << 1){
RD(a[i], b[i], w[i]), a[i|1] = b[i], b[i|1] = a[i], w[i|1] = w[i];
nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;
nxt[i] = hd[a[i]], hd[a[i]] = i;
}
FLC(rt, true), p[1] = -1, dfs(), p[1] = 0;
// Interaction Phase ...
int a, b; char cmd[5];
while (true){
RS(cmd); if (cmd[0] == 'C') RD(a, b), Modify(h[a], b);
else if (cmd[0] == 'Q') RD(a, b), Query(a, b);
else break;
}
// Rececling ....
RST(hd, p, l, r);
}
}
