rockdu
题目描述
给出一棵边带权的节点数量为n的树，初始树上所有节点都是白色。有两种操作：
C x，改变节点x的颜色，即白变黑，黑变白
A，询问树中最远的两个白色节点的距离，这两个白色节点可以重合(此时距离为0)。
输入输出格式
输入格式：
In the first line there is an integer N (N <= 100000)
In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of value c (-1000 <= c <= 1000)
In the next line, there is an integer Q denotes the number of instructions (Q <= 200000)
In the next Q lines, each line contains an instruction "C a" or "A"
输出格式：
For each "A" operation, write one integer representing its result. If there is no white node in the tree, you should write "They have disappeared.".
输入输出样例
捉迷藏的升级版，做法见：传送门。只是要注意边权可以为负，所以初值要赋值-inf。
第一次见这个题应该是在半年前了，外出集训看到这道题，根本不知所措。今天终于把这坑了半年的题填了。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
}e[maxn << 1];
int head[maxn], cnt, tot, ans;
void adde(const int &u, const int &v, const int &w) {
e[++cnt] = (edge) {v, w, head[u]};
head[u] = cnt;
}
struct Heap {
priority_queue<int > M, D;
void push(int x) {M.push(x);}
void del(int x) {D.push(x);}
void pop() {
while(!M.empty() && !D.empty() && M.top() == D.top())
M.pop(), D.pop();
M.pop();
}
int top() {
while(!M.empty() && !D.empty() && M.top() == D.top())
M.pop(), D.pop();
return M.empty() ? -inf : M.top();
}
int Qms() {
int mx1 = top(), mx2, ans;
if(mx1 == -inf) return 0;
pop(), mx2 = top();
if(mx2 == -inf) return push(mx1), 0;
return push(mx1), mx1 + mx2;
}
} Ans[maxn], Nd[maxn], All;
int size[maxn], mx[maxn], G, vis[maxn];
void FG(int u, int f, int & G, int tot) {
size[u] = 1, mx[u] = 0;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(vis[v] || v == f) continue;
FG(v, u, G, tot), size[u] += size[v];
mx[u] = max(mx[u], size[v]);
}
mx[u] = max(mx[u], tot - size[u]);
if(mx[u] < mx[G]) G = u;
}
int LG[maxn], fa[maxn], lyr[maxn], Dp[maxn][22], Tp[maxn], Ap[maxn];
void GetInit(int u, int f, int G, int L, int w) {
size[u] = 1;
Dp[u][L] = w, Nd[G].push(w);
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(vis[v] || v == f) continue;
GetInit(v, u, G, L, w + e[i].w);
size[u] += size[v];
}
}
void solve(int u, int rt, int L, int fw) {
int v, tmp;
GetInit(rt, 0, u, L, fw), vis[u] = 1, lyr[u] = L;
for(register int i = head[u]; i; i = e[i].next) {
v = e[i].v;
if(vis[v]) continue;
G = 0, FG(v, 0, G, size[v]), tmp = G;
fa[G] = u, solve(G, v, L + 1, e[i].w);
Tp[tmp] = Nd[tmp].top();
Ans[u].push(Tp[tmp]);
}
Ans[u].push(0);
All.push(Ap[u] = Ans[u].Qms());
}
void CG(int u) {
if(!LG[u]) ++tot, LG[u] = 1, Ans[u].del(0);
else --tot, LG[u] = 0, Ans[u].push(0);
int tmp, p = u, as = Ans[u].Qms(), fp = fa[p];
if(Ap[u] != as) All.push(as), All.del(Ap[u]), Ap[u] = as;
while(fp) {
if(!LG[u]) Nd[p].push(Dp[u][lyr[p]]);
else Nd[p].del(Dp[u][lyr[p]]);
tmp = Nd[p].top();
if(Tp[p] != tmp) {
if(Tp[p] != -inf) {Ans[fp].del(Tp[p]);}
if(tmp != -inf) {Ans[fp].push(tmp);}
Tp[p] = tmp;
}
as = Ans[fp].Qms();
if(Ap[fp] != as)
All.push(as), All.del(Ap[fp]), Ap[fp] = as;
p = fa[p], fp = fa[p];
}
}
char s[3];
int n, m, u, v, w, root;
int main() {
mx[0] = inf;
scanf("%d", &n);
for(register int i = 1; i < n; ++i)
scanf("%d%d%d", &u, &v, &w), adde(u, v, w), adde(v, u, w);
G = 0, FG(1, 0, G, n), root = G;
solve(G, 1, 0, 0);
scanf("%d", &m);
for(register int i = 1; i <= m; ++i) {
scanf("%s", s);
if(s[0] == 'A')
if(tot != n) printf("%d\n", All.top());
else printf("They have disappeared.\n");
else scanf("%d", &u), CG(u);
}
return 0;
}
没有帐号? 立即注册