problem
贼眉鼠眼有一棵 \(N\) 个节点的树，这棵树很特殊，每条边都有边权和颜色。
果宝特攻会不定时来进攻贼眉鼠眼。具体地，在前 \(Q\) 个时刻，在每个时刻，会发生以下两个事件之一：
-
果宝特攻摧毁了树上的一个节点 \(u\)。
-
贼眉鼠眼修复了树上的一个节点 \(u\)。
定义一条简单路径指图中没有重复节点的路径。简单路径的长度定义为路径上所有边的边权之和。
定义这棵树的能量值为以下满足条件的简单路径的长度的最大值：该简单路径的边颜色均为 \(c\)，且该简单路径包含所有颜色为 \(c\) 的边。
贼眉鼠眼想知道对于每个时刻，它的树的能量值为多少，以抵御果宝特攻的进攻。
100% 的数据：\(N,Q\le2×10^5,w_i\le 10^9,u_i,v_i,c_i\le N\)。
solution
就是将每种颜色的边拎出来，如果对于一种颜色它不是链则丢掉，否则只有当链上的点全部存活它才能有贡献。
将边与边用并查集合并可以得到一个 \(O(\deg)\) 的插入，不支持删除，所以线段树分治。那就更加糟糕了，没有前途。
考虑在树上搞这个东西，将一个点 \(u\) 的边分成向上的和经过自己的。可以对颜色定义 \(top_c\) 表示深度最浅的点，然后将这个颜色挂在 \(top_c\) 上。修改 \(u\) 的时候，将 \(top_c=u\) 的封掉，将自己上去的颜色封掉，可以用线段树维护颜色（区间加，全局最大值）。
code
点击查看代码
#include <cstdio>
#include <vector>
#include <cstring>
#include <tuple>
#include <numeric>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template<int N> struct segtree{
pair<int,LL> ans[N<<2]; int tag[N<<2];
void maintain(int p){ans[p]=max(ans[p<<1],ans[p<<1|1]);}
void spread(int p,int k){ans[p].first+=k,tag[p]+=k;}
void pushdown(int p){if(tag[p]) spread(p<<1,tag[p]),spread(p<<1|1,tag[p]),tag[p]=0;}
void build(function<LL(int)> w,int p,int l,int r){
tag[p]=0;
if(l==r) return ans[p]={0,w(l)},void();
int mid=(l+r)>>1;
build(w,p<<1,l,mid);
build(w,p<<1|1,mid+1,r);
maintain(p);
}
void modify(int L,int R,int k,int p,int l,int r){
if(L>R) return ;
if(L<=l&&r<=R) return spread(p,k);
int mid=(l+r)>>1; pushdown(p);
if(L<=mid) modify(L,R,k,p<<1,l,mid);
if(mid<R) modify(L,R,k,p<<1|1,mid+1,r);
maintain(p);
}
};
template<int N,int M> struct graph{
int head[N+10],nxt[M<<1],cnt;
struct edge{int u,v,w,c;} e[M<<1];
graph():cnt(0){memset(head,0,sizeof head);}
edge&operator[](int i){return e[i];}
int add(int u,int v,int w,int c){
e[++cnt]={u,v,w,c},nxt[cnt]=head[u];
return head[u]=cnt;
}
};
int n,m,deg[1<<18],top[1<<18],dep[1<<18];
LL sumw[1<<18];//for color
vector<int> buc[1<<18],pcs[1<<18];
graph<1<<18,1<<18> g;
segtree<1<<18> t;
void getsumw(){
dep[0]=1e9;
for(int c=1;c<=n;c++){
int cnt[3]={0,0,0};
LL tot=0;
for(auto i:buc[c]){
tot+=g[i].w;
for(int u:{g[i].u,g[i].v}){
if(deg[u]>=2){sumw[c]=-1; continue;}
cnt[deg[u]]--,cnt[++deg[u]]++;
if(dep[top[c]]>dep[u]) top[c]=u;
}
}
if(cnt[1]!=2) sumw[c]=-1;
if(sumw[c]!=-1) sumw[c]=tot,pcs[top[c]].push_back(c),debug("sumw[%d]=%d,top=%d\n",c,sumw[c],top[c]);
for(auto i:buc[c]) deg[g[i].u]=deg[g[i].v]=0;
}
}
int upc[1<<18];
void dfs(int u,int f){
dep[u]=dep[f]+1;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v; if(v==f) continue;
dfs(v,u),upc[v]=g[i].c;
}
}
int Lpos[1<<18],dfn[1<<18],rnk[1<<18],dfncnt,Q;
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d%d",&n,&Q);
for(int i=1,u,v,w,c;i<n;i++){
scanf("%d%d%d%d",&u,&v,&w,&c);
g.add(u,v,w,c),g.add(v,u,w,c);
buc[c].push_back(g.cnt);
}
dfs(1,0),getsumw();
for(int i=1;i<=n;i++){
Lpos[i]=m+1;
for(int c:pcs[i]) rnk[dfn[c]=++m]=c;
}
if(!m){
for(int i=1;i<=Q;i++) puts("0");
return 0;
}
t.build([&](int i){return sumw[rnk[i]];},1,1,m);
for(int op,u;Q--;){
scanf("%d%d",&op,&u);
op=(op==1?-1:1);
if(pcs[u].size()) t.modify(Lpos[u],Lpos[u]+pcs[u].size()-1,op,1,1,m);
if(dfn[upc[u]]) t.modify(dfn[upc[u]],dfn[upc[u]],op,1,1,m);
pair<int,LL> res=t.ans[1];
if(res.first<0||res.second<0) puts("0");
else printf("%lld\n",res.second);
}
return 0;
}