2023ICPC济南站：B. Graph Partitioning 2

题意问你有多少种删边的方法使得树剩下的连通块大小为k或者k+1。

这个题我不太会，但是我凭感觉打了一个暴力，居然也能AC。

不妨设1为根节点，如果某个节点连向父亲的边被删除，那么就可以根据$siz[x]$来判断子树里面分出了多少个$k$和$k+1$。

因为我们要考虑如果当前$x$连向父亲的边被删除以后的方案数，然后我们记录一个点的子树里面删掉$t$个点的方案数，这样只需要判断是否有$siz[x]-k$或者$siz[x]-k-1$就可以知道$x$连向父亲的边可不可以被删除。

这个记录只需要记录删除个数大于等于$siz[x]-k-1$的个数即可，直觉告诉我这个数量不是很多，所以直接把每个节点的儿子用背包合并即可。

#include
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){
    x=0;int f=0;char s=getchar();
    while(!isdigit(s))f|=s=='-',s=getchar();
    while(isdigit(s))x=x*10+s-48,s=getchar();
    x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){
    if(x<0)putchar('-'),x=-x;
    do{buf[++cc]=int(x%10);x/=10;}while(x);
    while(cc)putchar(buf[cc--]+'0');
}
const int N=1e5+10,mod=998244353;
int n,k,siz[N];
vector<int>e[N];
struct node{
    int val,num;
    node(int xx=0,int yy=0):val(xx),num(yy){}
};
vector<node>dp[N];
bool cmp(node p1,node p2){return p1.val<p2.val;}
int tp;node sta[N*10];
void dfs(int x,int fa){
    for(int y:e[x]){
        if(y==fa)continue;
        dfs(y,x);
    }
    siz[x]=1;
    dp[x].push_back(node(0,1));
    for(int y:e[x]){
        if(y==fa)continue;
        siz[x]+=siz[y];
        tp=0;
        for(node p1:dp[x])for(node p2:dp[y]){
            if(p1.val+p2.val>=siz[x]-k-1){
                sta[++tp]=node(p1.val+p2.val,1ll*p1.num*p2.num%mod);
            }
        }
        sort(sta+1,sta+tp+1,cmp);
        int t=min(1,tp);
        rep(i,2,tp){
            if(sta[t].val==sta[i].val){
                sta[t].num=(sta[t].num+sta[i].num)%mod;
            }
            else{
                sta[++t]=sta[i];
            }
        }
        vector<node>().swap(dp[x]);
        vector<node>().swap(dp[y]);
        rep(i,1,t)dp[x].push_back(sta[i]);
    }
    int ans=0;
    for(node p:dp[x])if(p.val==siz[x]-k||p.val==siz[x]-k-1)ans=(ans+p.num)%mod;
    if(ans)dp[x].push_back(node(siz[x],ans));
}
void solve(){
    qr(n),qr(k);
    rep(i,1,n){
        e[i].clear();
        dp[i].clear();
    }
    rep(i,1,n-1){
        int x,y;qr(x),qr(y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0);
    int ans=0;
    for(node p:dp[1])if(p.val==n)ans=(ans+p.num)%mod;
    cout<<ans<<endl;
}
int main(){
    int tt;qr(tt);
    while(tt--)solve();
    return 0;
}

后面题解是根号分治，主要是我一开始不太明白为什么

t=sqrt(n);
for(int y:e[x]){
	rep(i,1,min(t,siz[x]))
		rep(j,1,min(t,siz[y]))
			dp[]...
}

这样不会超时，后面才知道这样的复杂度是$O(nt)$的。

考虑树的dfs序，每次操作就是把两个区间合并， 那么我们每次合并就把交界处两边的t个点互相连边，那么任何两个点之间最多1条边，如果两个点距离超过2t，就不会再连边，因此连边的总数是$O(nt)$的。