1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
*ooh++ = c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) print('0');
else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
const int N = 100005;
int n, num, T, cnt, wfa[N], idfn[N], dfn[N], id[N], fa[N], top[N], siz[N], dep[N], h[N], pre[N<<1], e[N<<1], w[N<<1], mx[N<<2];
inline void add(int x, int y, int z){ e[++num]=y, w[num]=z, pre[num]=h[x], h[x]=num;}
void dfs1(int u){
siz[u]=1;
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa[u])
id[i>>1]=e[i], fa[e[i]]=u, wfa[e[i]]=w[i], dep[e[i]]=dep[u]+1, dfs1(e[i]), siz[u]+=siz[e[i]];
}
void dfs2(int u){
dfn[u]=++cnt;
int son=0;
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa[u] && siz[e[i]]>siz[son]) son=e[i];
if(son) top[son]=top[u], dfs2(son);
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa[u] && e[i]!=son)
top[e[i]]=e[i], dfs2(e[i]);
}
void build(int l, int r, int t){
if(l==r) return (void)(mx[t]=wfa[idfn[l]]);
int mid=l+r>>1, k=t<<1;
build(l, mid, k), build(mid+1, r, k|1);
mx[t]=max(mx[k], mx[k|1]);
}
void modify(int l, int r, int t, int x, int y){
if(l==r) return (void)(mx[t]=y);
int mid=l+r>>1, k=t<<1;
if(x<=mid) modify(l, mid, k, x, y); else modify(mid+1, r, k|1, x, y);
mx[t]=max(mx[k], mx[k|1]);
}
int query(int l, int r, int t, int L, int R){
if(L>R) return 0;
if(L<=l && r<=R) return mx[t];
int mid=l+r>>1, k=t<<1;
return max(L<=mid?query(l, mid, k, L, R):0, R>mid?query(mid+1, r, k|1, L, R):0);
}
int main() {
read(T);
while(T--){
num=1, cnt=0, memset(h, 0, sizeof h);
read(n);
for(int i=1; i<n; ++i){
static int x, y, z;
read(x), read(y), read(z);
add(x, y, z), add(y, x, z);
}
dfs1(1), top[1]=1, dfs2(1);
for(int i=1; i<=n; ++i) idfn[dfn[i]]=i;
build(1, n, 1);
while(1){
char opt;
int x, y;
while(isspace(opt=read()));
if(opt=='D') break; else read(x), read(y);
if(opt=='Q'){
int ans=0;
while(top[x]!=top[y])
if(dep[top[x]]<dep[top[y]])
ans=max(ans, query(1, n, 1, dfn[top[y]], dfn[y])), y=fa[top[y]];
else ans=max(ans, query(1, n, 1, dfn[top[x]], dfn[x])), x=fa[top[x]];
print(max(ans, query(1, n, 1, min(dfn[x], dfn[y])+1, max(dfn[x], dfn[y])))), print('\n');
}
else if(opt=='C') modify(1, n, 1, dfn[id[x]], y);
}
}
return flush(), 0;
}
|