题意
给出一棵边带权的节点数量为 的树,初始树上所有节点都是白色。有两种操作:
- :改变节点x的颜色,即白变黑,黑变白。
- :询问树中最远的两个白色节点的距离,这两个白色节点可以重合 (此时距离为 ) 。
分析
无脑上点分树,每个节点维护两个堆 维护子树中最大的长度 , 自己对父亲的贡献的最大长度。那么答案就是某一个节点 的权值,就是最大值加次大值。那么点分树维护一下就好了。轻微卡常。总复杂度为 。
代码
#include<bits/stdc++.h> using namespace std; #define ll long long int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();} return f ? -x : x; } const int N = 1e5 + 100,inf = 0x3f3f3f3f; struct Heap { priority_queue<int> s,t; void add(int x) {s.push(x);} void del(int x) {t.push(x);} void pre() {while(t.size() && s.top() == t.top()) s.pop(),t.pop();} int size() {return s.size() - t.size();} int top() { pre();if(s.size()) return s.top(); else -inf; } int top2() { int x = top();del(x);int y = top();add(x); return y; } int ans() { if(size() >= 2) return top() + top2(); else if(size() == 1) return max(top(),0); else return -inf; } }A[N],B[N],Ans; int n,col[N],cnt,Log[N]; struct Edge {int to,nxt,w;}e[N << 1]; int fa[N][21],dep[N],dis[N],head[N],ecnt; void addedge(int x,int y,int w) {e[++ecnt]=(Edge){y,head[x],w};head[x] = ecnt;} int lca(int x,int y) { if(dep[x] < dep[y]) swap(x,y); int k = dep[x] - dep[y];for(int i = Log[k];~i;i--) { if((k >> i) & 1) x = fa[x][i]; }if(x == y) return x; for(int i = Log[dep[x]];~i;i--) { if(fa[x][i] ^ fa[y][i]) x = fa[x][i],y = fa[y][i]; }return fa[x][0]; } int dist(int x,int y) {return dis[x] + dis[y] - 2 * dis[lca(x,y)];} void Init(int x,int Fa,int Dep) { fa[x][0] = Fa;dep[x] = Dep; for(int i = 1;i <= Log[dep[x]];i++) fa[x][i] = fa[fa[x][i-1]][i-1]; for(int i = head[x];i;i = e[i].nxt) { int y = e[i].to;if(y == Fa) continue; dis[y] = dis[x] + e[i].w;Init(y,x,Dep+1); } } int rt,maxs[N],size[N],vis[N],dfa[N]; void getrt(int x,int Fa,int tots) { size[x] = 1;maxs[x] = 0; for(int i = head[x];i;i = e[i].nxt) { int y = e[i].to;if(vis[y] || y == Fa) continue; getrt(y,x,tots);size[x] += size[y]; maxs[x] = max(maxs[x],size[y]); }maxs[x] = max(tots - size[x],maxs[x]); if(maxs[rt] > maxs[x]) rt = x; } void getdis(int x,int Fa,int Di,int rot) { B[rot].add(Di);for(int i = head[x];i;i = e[i].nxt) { int y = e[i].to;if(y == Fa || vis[y]) continue; getdis(y,x,Di + e[i].w,rot); } } void Add(int x) {if(A[x].size() >= 2) Ans.add(A[x].ans());} void Del(int x) {if(A[x].size() >= 2) Ans.del(A[x].ans());} void rebuild(int x,int Fa,int tots) { vis[x] = 1; for(int i = head[x];i;i = e[i].nxt) { int y = e[i].to;if(vis[y]) continue; maxs[rt = 0] = inf; int Tot = (size[x] < size[y]) ? tots - size[x] : size[y]; getrt(y,x,Tot); getdis(y,x,e[i].w,rt); A[x].add(B[rt].top());dfa[rt] = x; rebuild(rt,x,Tot); }A[x].add(0);Add(x); } void update(int x) { !col[x] ? --cnt : ++cnt;col[x] = 1 - col[x]; if(col[x]) {Del(x);A[x].del(0);Add(x);} else {Del(x);A[x].add(0);Add(x);} for(int now = x;dfa[now];now = dfa[now]) { int F = dfa[now],d = dist(x,F); if(col[x]) { Del(F); if(B[now].size()) A[F].del(B[now].top()); if(B[now].size()) B[now].del(d); if(B[now].size()) A[F].add(B[now].top()); Add(F); } else { Del(F); if(B[now].size()) A[F].del(B[now].top()); B[now].add(d); A[F].add(B[now].top()); Add(F); } } } int query() { if(cnt >= 2) return max(Ans.top(),0); else if(cnt == 1) return 0; else return -inf; } int main() { n = read(); for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1; for(int i = 1,u,v,w;i < n;i++) { u = read();v = read();w = read(); addedge(u,v,w);addedge(v,u,w); }Init(1,0,1);maxs[rt = 0] = inf;getrt(1,0,n); rebuild(rt,0,n);int Q = read();cnt = n; while(Q--) { char ch[10];scanf("%s",ch + 1); if(ch[1] == 'A') { int res = query(); if(res <= -inf) printf("They have disappeared.\n"); else printf("%d\n",res); } else {int x = read();update(x);} } return 0; }