这个做法。。。纯粹。。。。恶心自己。。。。泪奔。。。。
# 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; }