- https://codeforces.com/contest/1787
- TypeDB Forces 2023 (Div. 1 + Div. 2) C (dp) D(dfs), 严格鸽
- TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!), Immortality
Problem G. Colorful Tree Again
题意：给定一个边权图，初始固定每个边有颜色和边权。每个节点也有颜色，初始都是黑色。
每次操作可以改变一个节点的颜色，并询问当前最大的好的路径的权值和是多少。
一个路径是好的，当且仅当路径上的所有点颜色相同，并包含了所有该颜色的边，且路径上经过的所有节点的颜色为白。
解法：这个题首先第一反应是 QTREE 4 和 QTREE 6 的某种结合。。。 但是仔细读题发现判定的条件是 path 而不是 component ！！！
因而题目难度大幅简化。。。但是想写得简洁依然会很困难。。。
首先第一步当然是剔除不合法的颜色。。。（最好用度数做简单的判定，不要在 dfs() 的时候判定。。）
然后再 dfs() 的时候，剩下的路径都有且仅有一个最高点。。我们对所有最高点位 u 的路径都放在一个堆里维护，记做 Q[u]…
那么在用所有的 Q[u] 组织一个堆来维护最优解。。（类似动态直径问题的点分树做法里最有的堆。。。）
那么每次 toggle 一个点时，除了会影响 Q[u].. 还会影响 u 向上的一条路径。。
记录那条路径所在的堆为 Q[y]，那么如果现在 Q[y] 包含在 ans 里时，更新 Q[y] 前后还要顺手更新一下 ans。
无论那种情况，我们现在都可以 O(1) 的 push()、pop() 操作进行处理。。
那么我们只需要实现一个可删除堆即可。。。stl 里的堆自然是不可定向删除的。。。
所以现在主流的 Dijkstra 模板里要求可删除堆的时候。。其实我们都是做延迟处理。。（尽管 clrs 里其实有可删除堆的相关代码。）
这里我们也可以用类似的方法。。。
对于每个堆，再开一个辅助堆，记录删除过的值即可。。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(2e5) + 9;
struct heap {
priority_queue<LL>Q, q;
void push(LL x){if(x)Q.push(x);}
void pop(LL x){if(x)q.push(x);}
LL top() {
while(!q.empty() && Q.top() == q.top()) Q.pop(), q.pop();
if (Q.empty()) return 0;
return Q.top();
}
};
vector<pair<int, PII>> adj[N]; map<int, int> sub[N]; heap Q[N], ans;
LL W[N]; bool path[N], bad[N]; int top[N], upc[N], del[N];
// 颜色的权值和，该颜色是否组成路径，节点是否已损坏，颜色的最高代表点，点到父亲的边的颜色，除最高点外路径被阻塞的次数
int n;
void dfs(int u = 1, int p = 0) {
for (auto e: adj[u]) {
int v = e.fi; if (v == p) continue;
int w = e.se.fi, c = e.se.se;
if (!top[c]) top[c] = u;
upc[v] = c; dfs(v, u);
}
}
void fix(int x) {
if (bad[x]) {
ans.pop(Q[x].top());
if (x != 1) {
int c = upc[x]; if (!path[c]) return;
if (del[c]++) return;
int y = top[c];
if (!bad[y]) ans.pop(Q[y].top());
Q[y].pop(W[c]);
if (!bad[y]) ans.push(Q[y].top());
}
} else {
ans.push(Q[x].top());
if (x != 1) {
int c = upc[x]; if (!path[c]) return;
if (--del[c]) return;
int y = top[c];
if (!bad[y]) ans.pop(Q[y].top());
Q[y].push(W[c]);
if (!bad[y]) ans.push(Q[y].top());
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int q; RD(n, q); DO(n-1) {
int x, y, w, c; RD(x, y, w, c); ++sub[c][x]; ++sub[c][y]; W[c] += w;
adj[x].PB({y, {w, c}}); adj[y].PB({x, {w, c}});
}
dfs();
REP_1(c, n) if (W[c]) {
int c1 = 0; path[c] = 1;
for (auto e: sub[c]) {
if (e.se == 1) ++c1;
else if (e.se != 2) {
path[c] = 0;
break;
}
}
path[c] &= c1 == 2;
if (path[c]) Q[top[c]].push(W[c]);
}
REP_1(i, n) ans.push(Q[i].top());
DO(q) {
int p, x; RD(p, x); bad[x] = !p; fix(x);
printf("%lld\n", ans.top());
}
}
