题意简述
\(n\) 个节点的无根树，边有长度和颜色，一条好的路径上边颜色相同，点都没被摧毁，且包含树上所有该颜色的边，一次操作摧毁或恢复一个节点，每次操作后询问最长的好的路径。
思路
\(\text{devin}\) 布置的题单里的一题，昨天听wy和why叫了一个下午：“这是一颗树啊！~”
只可惜，一开始还是没有觉得这一点有什么用。
首先很显然可以先预处理把所有好的路径找出来，为了方便用路径的颜色作为它的编号，每次摧毁恢复点只会使一些好的路径出现或消失，而不会改变它们的长度。至于怎么找，可以参考判链的方式，若对于一种颜色 \(c\) ，每个节点有颜色 \(c\) 的度数均不超过 \(2\)，且度数为 \(1\) 的点恰有 \(2\) 个，那么可以判定 \(c\) 对应的路径为好的。
然后就磕死在这里了，如果每次操作记录下每条好的路径的改变情况，那放个菊花图不瞬间复杂度爆炸了……
经wy的点醒：“这是一颗树呀！~”，我脱口而出：“每个节点只有一个爸爸！”
于是发现了关键的突破口，虽然好的路径可能有很多条，但有些路径其实是可以归为一类的。
考虑删掉一个点 \(x\) 对哪些路径会产生影响，一类是从它的子节点上来再下去的这种挂在 \(x\) 上的，另一类是从子节点上来往祖先那去的，发现第二类最多只有一条路径。
可以在每一个节点上开一个 \(\text{set}\) ，存第一类中挂在节点 \(x\) 上的路径长度。再把每个节点上的最长的长度加入全局的一个 \(\text{set}\) 。
对于摧毁一个点 \(x\)：对 \(x\) 节点上的 \(\text{set}\) 打上一个删除 \(\text{tag}\) ，并从全局的 \(\text{set}\) 中把节点 \(x\) 的最大值删去。如果 \(x\) 到 \(fa_x\) 的边属于一条好的路径，就从对应的 \(\text{set}\) 中删去它的值。
对于恢复一个点，类似。
但如果直接这样做一条路径可能被删很多次，可以多记录一下除该路径的 \(\text{lca}\) 外摧毁了几个点。
细节比较多，写挂了很多次，主要是处理删一个集合和删单条路径的关系时出了些锅（比如删了一个集合就不可能把恢复的路径加入到答案里），所幸靠样例就调出来了。(用 \(\text{set}\) 的时候时刻考虑插入删除的元素是否可能不存在，\(\text{multiset}\) 里相同元素只删一个要先find)
时间复杂度 \(O(q \log n)\)
Code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define mpr make_pair
//mt19937_64 ra(time(0) ^ (*new char));
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
const ll SIZE = 200005;
const ll mod = 998244353;
ll n, T;
ll head[SIZE], ver[SIZE*2], nxt[SIZE*2], val[SIZE*2], col[SIZE*2], tot;
ll len[SIZE], las[SIZE];
ll cnt2[SIZE], cnt1[SIZE], use[SIZE], tt[SIZE], vis[SIZE];
ll id[SIZE];
multiset<ll> s[SIZE], ans;
ll gg[SIZE], tag[SIZE];
inline ll rd(){
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x*f;
}
void add(ll x, ll y, ll v, ll c){
ver[++tot] = y, nxt[tot] = head[x];
head[x] = tot; val[tot] = v, col[tot] = c;
}
void dfs(ll x, ll fa, ll fr){
las[x] = fr;
for(ll i = head[x]; i; i = nxt[i]){
ll y = ver[i];
tt[col[i]]++;
}
for(ll i = head[x]; i; i = nxt[i]){
ll y = ver[i];
if(vis[col[i]]) continue;
vis[col[i]] = 1;
if(tt[col[i]] == 1) cnt1[col[i]]++;
else if(tt[col[i]] == 2) cnt2[col[i]]++;
else use[i] = 0;
}
for(ll i = head[x]; i; i = nxt[i]){
ll y = ver[i];
vis[col[i]] = 0, tt[col[i]]--;
}
for(ll i = head[x]; i; i = nxt[i]){
ll y = ver[i];
if(y == fa) continue;
dfs(y, x, col[i]);
}
}
void dfs1(ll x, ll fa){
for(ll i = head[x]; i; i = nxt[i]){
ll y = ver[i];
if(y == fa) continue;
if(!vis[col[i]]){
vis[col[i]] = 1;
if(use[col[i]]){
id[col[i]] = x;
s[x].insert(len[col[i]]);
}
}
dfs1(y, x);
}
if(!s[x].empty()) ans.insert(*s[x].rbegin());
}
int main(){
n = rd(), T = rd();
for(ll i = 1; i < n; i++){
ll x = rd(), y = rd(), v = rd(), c = rd();
add(x, y, v, c); add(y, x, v, c);
len[c] += v; use[i] = 1;
} use[n] = 1;
dfs(1, 0, 0);
for(ll i = 1; i <= n; i++){
if(cnt1[i] != 2) use[i] = 0;
}
dfs1(1, 0);
while(T--){
ll tp = rd(), x = rd();
if(tp){
tag[x] = 0;
if(!s[x].empty()) ans.insert(*s[x].rbegin());
if(use[las[x]]){
gg[las[x]]--;
if(gg[las[x]] == 0){
if(!s[id[las[x]]].empty() && !tag[id[las[x]]]) ans.erase(ans.find(*s[id[las[x]]].rbegin()));
s[id[las[x]]].insert(len[las[x]]);
if(!tag[id[las[x]]]) ans.insert(*s[id[las[x]]].rbegin());
}
}
}
else{
tag[x] = 1;
if(!s[x].empty()) ans.erase(ans.find(*s[x].rbegin()));
if(use[las[x]]){
if(gg[las[x]] == 0 && !s[id[las[x]]].empty()){
if(tag[id[las[x]]] == 0) ans.erase(ans.find(*s[id[las[x]]].rbegin()));
s[id[las[x]]].erase(s[id[las[x]]].find(len[las[x]]));
if(!s[id[las[x]]].empty() && tag[id[las[x]]] == 0) ans.insert(*s[id[las[x]]].rbegin());
}
gg[las[x]]++;
}
}
if(!ans.empty()) printf("%lld\n", *ans.rbegin());
else printf("0\n");
}
return 0;
}