这个做法。。。纯粹。。。。恶心自己。。。。泪奔。。。。
# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
# include <vector>
using namespace std;
const int SIZE = 10007;
const int INF = 2147483647;
int t, n;
struct EDGE { int v, next, len; } e[SIZE<<1];
int h[SIZE], tot, Edgesign[SIZE];
void AddEdge(int u, int v, int len)
{
e[++tot].v = v;
e[tot].len = len;
e[tot].next = h[u];
h[u] = tot;
}
bool vis[SIZE];
int tree[(SIZE<<1)<<2], pos[(SIZE<<1)<<2], M;
int list[SIZE<<1], firstshow[SIZE], ltot;
int tsize[SIZE], Ednode[SIZE], dist[SIZE];
int Generfa(int s, int t)
{
s = firstshow[s];
t = firstshow[t];
if ( s > t ) swap(s, t);
int ans = 0, min = INF;
for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1)
{
if (~s&1 && tree[s^1] < min) min = tree[s^1], ans = pos[s^1];
if ( t&1 && tree[t^1] < min) min = tree[t^1], ans = pos[t^1];
}
return list[ans];
}
inline void Intree(int &x, int &d)
{
tree[M + (++ltot)] = d;
list[ltot] = x;
pos[M+ltot] = ltot;
if ( firstshow[x] == 0 ) firstshow[x] = ltot;
}
void LCA(int x, int d)
{
vis[x] = true;
Intree(x, d);
tsize[x] = 1;
dist[x] = d;
for (int i = h[x]; i; i = e[i].next)
{
if ( vis[e[i].v] ) continue;
LCA(e[i].v, d+1);
Intree(x, d);
tsize[x] += tsize[e[i].v];
Ednode[e[i].v] = e[i].len; //边权加在点上
}
vis[x] = false;
}
class Sgttree
{
public:
vector <int> tree;
int size, M;
void Init(int insize)
{
size = insize; tree.clear();
if ( size == 1 ) tree.resize(7);
else tree.resize(size<<2);
for (M = 1; M <= size + 1; M <<= 1);
for (int i = (size<<2) - 1; i; --i ) tree[i] = -INF;
}
void Build()
{
for (int i = M - 1; i; --i )
if ( tree[i<<1] > tree[(i<<1)+1] ) tree[i] = tree[i<<1];
else tree[i] = tree[(i<<1)+1];
}
void Modify(int x, int n)
{
tree[n+=M] = x;
for ( n >>= 1; n; n >>= 1 ) tree[n] = max(tree[n<<1], tree[(n<<1)+1]);
}
int getmax(int s, int t)
{
int max = -INF;
if ( s > t ) swap(s, t);
for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1 )
{
if (~s&1 && tree[s^1] > max ) max = tree[s^1];
if ( t&1 && tree[t^1] > max ) max = tree[t^1];
}
return max;
}
}_st;
vector <Sgttree> sgtree;
int belong[SIZE], sgttot, sgtsize[SIZE], sgtpos[SIZE], pointpos[SIZE];
int firptr[SIZE]; //当前线段树中第一个节点编号
int fa[SIZE];
void SelcEdge(int x)
{
vis[x] = true;
int i, maxsize = -INF, which;
for (i = h[x]; i; i = e[i].next)
if ( !vis[e[i].v] && tsize[e[i].v] > maxsize ) maxsize = tsize[e[i].v], which = e[i].v;
for (i = h[x]; i; i = e[i].next)
{
if ( vis[e[i].v] ) continue;
if ( e[i].v == which )
{
if( belong[x] == -1 ) belong[e[i].v] = ++sgttot;
else belong[e[i].v] = belong[x];
}
else belong[e[i].v] = -1; //标记为轻边指向点
SelcEdge(e[i].v);
}
vis[x] = false;
}
inline void InsertSgt(int x)
{
int k = belong[x];
if ( sgtpos[k] == 0 ) firptr[k] = x;
sgtree[k].tree[sgtree[k].M + (++sgtpos[k])] = Ednode[x];
pointpos[x] = sgtpos[k];
}
void CreatSgt(int x)
{
vis[x] = true;
if ( belong[x] != -1 ) InsertSgt(x);
for (int i = h[x]; i; i = e[i].next )
{
if ( vis[e[i].v] ) continue;
CreatSgt(e[i].v);
fa[e[i].v] = x;
}
vis[x] = false;
}
void Init()
{
int i, a, b, c;
scanf("%d", &n);
memset(h, 0, sizeof(h));
memset(vis, 0, sizeof(vis));
memset(firstshow, 0, sizeof(firstshow));
memset(tree, 44, sizeof(tree));
memset(sgtsize, 0, sizeof(sgtsize));
memset(sgtpos, 0, sizeof(sgtpos));
sgtree.clear();
tot = ltot = sgttot = 0;
Ednode[1] = -INF;
for ( M = 1; M <= (n<<1)+1; M <<= 1 );
for (i = 1; i != n; ++i )
{
scanf("%d%d%d", &a, &b, &c);
AddEdge(a,b,c); Edgesign[i] = tot;
AddEdge(b,a,c);
}
LCA(1,0);
for (i = ltot+M; i; --i )
if ( tree[i>>1] > tree[i] ) tree[i>>1] = tree[i], pos[i>>1] = pos[i];
}
void change(int x, int a)
{
int b = e[ Edgesign[a]+1].v, k;
a = e[ Edgesign[a] ].v;
if( dist[a] < dist[b] ) a = b;
k = belong[a];
if ( k != -1 ) sgtree[k].Modify(x, pointpos[a]);
else Ednode[a] = x;
}
int find(int a, int b)
{
if ( a == b ) return 0;
int root = Generfa(a, b), ans = -INF, l, r;
for (int i = 0; i != 2; ++i, a = b )
for ( ;a && dist[a] > dist[root]; a = fa[a] )
if ( belong[root] == belong[a] && belong[a] != -1 )
{
l = min(pointpos[root], pointpos[a])+1;
r = max(pointpos[root], pointpos[a]);
ans = max( ans, sgtree[belong[root]].getmax(l, r) );
break;
}
else if ( belong[a] == -1 ) ans = max( ans, Ednode[a]);
else
{
ans = max( ans, sgtree[belong[a]].getmax(1,pointpos[a]) );
a = firptr[belong[a]];
}
return ans;
}
void Work()
{
int i, a, b;
char tmp[30];
belong[1] = -1; SelcEdge(1);
for (i = 1; i <= n; ++i ) if ( belong[i] > 0 ) ++sgtsize[ belong[i] ];
sgtsize[0] = 1;
for (i = 0; i <= sgttot; ++i ) //vector下表从0开始
{
_st.Init(sgtsize[i]);
sgtree.push_back(_st);
}
fa[1] = 1; CreatSgt(1);
for (i = 1; i <= sgttot; ++i ) sgtree[i].Build();
while( true )
{
scanf("%s", tmp);
if ( tmp[0] != 'D' ) scanf("%d%d", &a, &b);
else return ;
switch(tmp[0])
{
case 'Q': printf("%d\n", find(a, b)); break;
case 'C': change(b, a); break;
}
}
}
int main()
{
scanf("%d", &t);
while(t--)
{
Init();
Work();
}
return 0;
}