心在跳，不是白象的我不跳。

· · 题解

CF1787G，在物理期末考试前的诡异自习里搞出来了。

虽然说你对每个颜色都建虚树空间是 O(n) 的，但是分开维护没有出路，这是因为一个点连出的颜色数是 O(n) 的。考虑一朵菊花，反复操作菊花的根就可以使得每次要修改 O(n) 棵虚树的值。

那么考虑就放在这棵树上维护。（由于摧毁和修复是同理的所以下文只考虑摧毁）

显然所有好路径都是树链，摧毁一个点 u 会影响的路径就自然地分为两种：以 u 为根的链 和 根是 u 的祖先的链。

注意到第二种至多只有一条（每个点连向父亲的颜色唯一），那么对于每条链可以简单地维护有多少点被摧毁从而判断它是否产生贡献，而不需要知道具体哪些点被摧毁。

现在加上第一种链，对应操作就是取消所有以 u 为根的链的贡献。那么如果我们把每条链都挂在它的根处，使用单点修改、求全局最大值的数据结构维护以支持对于第二种链的修改，再在外面使用另一个同样的数据结构维护所有 挂了链的未被摧毁的点，其拥有的链的最大值 的最大值，那么就做完了。

我们可以使用平衡树或动态开点线段树，这样时间复杂度 O((n+q) \log n)，空间 O(n) 或 O(n \log n)。

实际上线段树部分只需要写 8 行（。
另外，注意找出每种颜色的链长和根时不要用链式前向星存图，使用 vector 将所有边按颜色排序可以做到 O(n \log n)。 

const int N = 200003, oo = 2e9;
int n,q,head[N],cntr,dep[N],lca[N];
int fir[N],cnt[N],col[N],siz[N]; bool S[N]; ll len[N];
struct Node{
    int to,w,c;
    inline bool operator <(const Node &a) const{ return c==a.c?w<a.w:c<a.c; }
}; vector<Node> e[N];
#define all(x) x.begin(),x.end()

inline void DFS(int u,int fa){
    dep[u]=dep[fa]+1,sort(all(e[u]));
    (u!=1&&dep[fir[col[u]]]<dep[u])&&(fir[col[u]]=u);
    for(auto t:e[u]){
        int v=t.to; if(v==fa) continue;
        (dep[fir[t.c]]<dep[v])&&(fir[t.c]=v),col[v]=t.c,DFS(v,u);
    }
}
inline void Get(int u,int fa,int c){
    (!lca[c]||dep[lca[c]]>dep[u])&&(lca[c]=u),++siz[c];
    for(auto it = upper_bound(all(e[u]),(Node){+oo,+oo,c-1}); it!=e[u].end()&&it->c==c; ++it)
        if(it->to!=fa){ int v=it->to; len[c]+=it->w,Get(v,u,c); break; }
}
template<const int SIZ> struct SegTree{
    struct Seg{ int lc,rc; ll val; }tr[SIZ]; int tot,root[N];
    inline void Push(int u){ tr[u].val=max(tr[tr[u].lc].val,tr[tr[u].rc].val); }
    inline void Mdf(int &u,int l,int r,int x,ll d){
        if(!u) u=++tot; if(l==r){ tr[u].val=d; return; } int mid=l+r>>1;
        x<=mid?Mdf(tr[u].lc,l,mid,x,d):Mdf(tr[u].rc,mid+1,r,x,d); Push(u);
    }
}; SegTree<N*20> t; SegTree<N<<1> T;

auto Lock = [](int u){
    T.Mdf(T.root[0],1,n,u,0);
    if(u==1) return; --siz[col[u]];
    if(lca[col[u]]&&siz[col[u]]==cnt[col[u]]-1){
        int LCA = lca[col[u]];
        t.Mdf(t.root[LCA],1,n,col[u],0);
        if(S[LCA]) T.Mdf(T.root[0],1,n,LCA,t.tr[t.root[LCA]].val);
    }
};
auto Unlock = [](int u){
    T.Mdf(T.root[0],1,n,u,t.tr[t.root[u]].val);
    if(u==1) return; ++siz[col[u]];
    if(lca[col[u]]&&siz[col[u]]==cnt[col[u]]){
        int LCA = lca[col[u]];
        t.Mdf(t.root[LCA],1,n,col[u],len[col[u]]);
        if(S[LCA]) T.Mdf(T.root[0],1,n,LCA,t.tr[t.root[LCA]].val);
    }
};

main(){
    rd(n),rd(q),fill(S+1,S+n+1,1);
    for(int i=1,u,v,w,c;i<n;++i)
        rd(u),rd(v),rd(w),rd(c),e[u].push_back({v,w,c}),e[v].push_back({u,w,c}),++cnt[c];
    for(int i=1;i<=n;++i) if(cnt[i]) ++cnt[i];
    DFS(1,0);
    for(int i=1;i<=n;++i) if(fir[i]){
        Get(fir[i],0,i); if(siz[i]!=cnt[i]){ len[i]=lca[i]=-1; continue; }
        t.Mdf(t.root[lca[i]],1,n,i,len[i]);
    }
    for(int i=1;i<=n;++i) if(t.root[i])
        T.Mdf(T.root[0],1,n,i,t.tr[t.root[i]].val);
    while(q--){
        int p,x; rd(p),rd(x),S[x]^=1;
        p?Unlock(x):Lock(x); writeln(T.tr[T.root[0]].val);
    }
}