零、前言
自闭场，( t D) 想复杂白给，结束前 (10) 分钟想出正确做法忘写树状数组，( t C,E) 赛后随便切 (...)
不要硬刚一道题，不要完全看过题人数来决定你做哪道题，( t think twice,code once)
《( t zxy) 掉大分》正在连载中 (...)
一、题目
给定 (n) 个点的树，每个点有一个度数 (d_i)，问有多少个满足下列条件的二元组 ((x,y))：
- (0leq xleq n)，并且存在选出 (x) 个点的方式使得其度数和为 (y)
(nleq 2cdot 10^5)
二、解法
首先我声明树这个背景没有任何卵用，根据 ( t purfer) 序列的理论，任何一种度数序列都能对应至少一棵树，问题又只和度数序列有关，既然树对度数序列没有任何限制那么可以不管他。
我们把所有 (d_i) 减少 (1)，那么问题变成了 (n) 个物品体积总和为 (n-2) 的背包问题，最烦的是要记录选了多少个物品。
Lamma：设 (L(x)) 表示总体积为 (x) 的最少物品数，(R(x)) 表示总体积为 (x) 的最多物品数，那么对于选出 (t) 个物品总和为 (x)，当且仅当 (L(x)leq tleq R(x)) 是可以实现的。
证明：必要性易得，下证充分性。
设体积为 (0) 的物品一共有 (z) 个，可以转证下列问题：
[R(x)-L(x)leq 2z+1 ]这是因为 (R(x)) 通过去掉体积为 (0) 的物品可以得到 (tin[R(x)-z,R(x)]) 的方案，(L(x)) 可以通过增加体积为 (0) 的物品得到 (tin[L(x),L(x)+z]) 的方案。
考虑任意一种背包方案权值和为 (k)，数量为 (c)，那么有：
[-zleq k-cleq z-2 ]因为让 (k-c) 最小直接选那些体积为 (0) 的物品，让 (k-c) 最大需要选体积大于 (0) 的物品：
[k-c=sum d_i-sum [d_i> 0]=n-2-(n-z)=z-2 ]那么 (k-L(x)) 和 (k-R(x)) 一定在 ([-z,z-2]) 这个范围里，所以 (R(x)-L(x)) 不超过 (2z-2)，证毕。
只需要用 (dp) 求出 (L(x),R(x)) 即可，因为物品种类数不超过 (sqrt n)，对于每一种物品，可以把体积按余数分类，对于每一种余数跑单调队列即可，时间复杂度 (O(nsqrt n))
三、总结
首先排除不必要的背景，比如本题树的背景对原问题没有任何限制那么是可以排除的。
对于难做的点，找必要条件猜结论。
最后物品种类数很少的背包问题，每种物品分别处理，按余数分类之后解决。
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 200005;
#define ll long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,z,c[M],d[M],p[M],mi[M],mx[M],dp[M];ll ans;
signed main()
{
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
d[u]++;d[v]++;
}
for(int i=1;i<=n;i++)
{
d[i]--,c[d[i]]++;
mi[i]=1e9,mx[i]=-1e9;
if(!d[i]) z++;
}
mi[0]=mx[0]=0;
//cal mx
for(int i=1;i<=n;i++)
{
int x=c[i];
if(!x) continue;
for(int j=0;j<=n;j++) dp[j]=mx[j];
for(int j=0;j<i;j++)
{
int l=1,r=0,nw=j;
for(int k=0;nw<=n;k++,nw+=i)
{
while(l<=r && p[l]<nw-i*x) l++;
if(l<=r) mx[nw]=max(mx[nw],dp[p[l]]+k-p[l]/i);
while(l<=r && dp[p[r]]-p[r]/i<=dp[nw]-nw/i) r--;
p[++r]=nw;
}
}
}
//cal mi
for(int i=1;i<=n;i++)
{
int x=c[i];
if(!x) continue;
for(int j=0;j<=n;j++) dp[j]=mi[j];
for(int j=0;j<i;j++)
{
int l=1,r=0,nw=j;
for(int k=0;nw<=n;k++,nw+=i)
{
while(l<=r && p[l]<nw-i*x) l++;
if(l<=r) mi[nw]=min(mi[nw],dp[p[l]]+k-p[l]/i);
while(l<=r && dp[p[r]]-p[r]/i>=dp[nw]-nw/i) r--;
p[++r]=nw;
}
}
}
//cal answer
for(int i=0;i<=n;i++)
if(mi[i]<=mx[i])
ans+=mx[i]-mi[i]+1+z;
printf("%lld
",ans);
}