题解：P11943 [KTSC 2025] 粒子对撞 / particles

· · 题解

为什么是紫？

对于给定的树，割去所有被关闭的点后，对于一个连通块，我们每次选出两个存在粒子的点，如果这两个点路径上还有存在粒子的点就去递归路径上的点，最后一定可以找到一个合法的可消除对，所以说，一个连通块的贡献就是粒子数除以 2 下取整。

怎么修改？考虑这样一个算法，割去一条边时，对于分裂出的两个连通块，随便找一个连通块 dfs，如果 dfs 了超过 \sqrt n 个点就停止并 dfs 另一侧连通块进行分裂，注意到每次分裂时总会发生以下情况之一：

  1. 两侧连通块大小都大于 \sqrt n 且 dfs 了一侧。

  2. dfs 了大小更小的那个连通块。

  3. 两侧连通块大小都小于 \sqrt n 且 dfs 了一侧。

注意到一个点在合并过程中所在集合要么大小小于 \sqrt n 新加入一个点要么大小翻倍要么大小增加至少 \sqrt n，所以总时间复杂度 O(n \sqrt n)。

代码很好写。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+114;
set<int> E[maxn];
int d[maxn];
int fa[maxn];
int tot;
int V[maxn<<1];
int vis[maxn];//0 1 -1
const int warma = 700;
int now;
void dfs(int u,int lst){
    now+=d[u];
    if(now>warma) return ;
    for(int v:E[u]){
        if(v!=lst){
            dfs(v,u);
            if(now>warma) return ;
        }
    }
}
void solve(int u,int lst,int root){
    fa[u]=root;
    V[root]+=(vis[u]==1);
    for(int v:E[u]) 
        if(v!=lst) solve(v,u,root);
}
int ans;
void Cut(int u,int v){
    E[u].erase(v);
    E[v].erase(u);
    now=0;
    dfs(u,-1);
    if(now>warma) swap(u,v);
    //solve(u)
    ans-=V[fa[u]]/2;
    ++tot;
    solve(u,-1,tot);
    V[fa[v]]-=V[fa[u]];
    ans+=V[fa[v]]/2+V[fa[u]]/2;
}
void initialize(int n, std::vector<int> A, std::vector<int> B){
    for(int i=0;i<n-1;i++){
        E[A[i]].insert(B[i]);
        E[B[i]].insert(A[i]);
    }
    for(int i=0;i<n;i++) d[i]=E[i].size();
    ++tot;
    solve(0,-1,tot);
}
int generate(int u, bool result){
    if(result==false){
        while(E[u].size()>0){
            int v=(*E[u].begin());
            Cut(u,v);
        }
    }
    vis[u]=(result==true?1:-1);
    ans-=V[fa[u]]/2;
    if(result==true) V[fa[u]]++;
    ans+=V[fa[u]]/2;
    return ans;
}