令$a_{i}$为$i$的度数-1，那么$(x,s)$合法即等价于存在$Ssubseteq [1,n],|S|=x$且$sum_{kin S}a_{k}=s$
引理：$(x,s)$合法的必要条件为$-zle s-xle z-2$
令$z$为$a_{i}$中为0的元素个数，考虑任意一个集合$Ssubseteq [1,n]$，显然$-zle sum_{kin S}a_{k}-|S|le z-2$
具体的，考虑该式即为$sum_{kin S}(a_{k}-1)$，那么将所有$a_{k}<1$的项求和即为最小值，将所有$a_{k}ge 1$的项求和即为最大值，不难发现前者即为$-z$，后者即为$sum_{i=1}^{n}a_{i}-(n-z)=z-2$
不难发现，其所描述的即为该引理，也即得证
结论：令$mn(s)=min_{(x,s)合法}x$和$mx(s)=max_{(x,s)合法}x$，则$forall mn(s)le xle mx(s),(x,s)$合法
（为了方便，若不存在$(x,s)$合法则定义$mn(s)$和$mx(S)$为$pminfty$，显然此时满足结论）
同样令$z$为$a_{i}$中为0的元素个数，显然$mn(s)$对应的方案必然一个0都不选，那么在其基础上再选$[0,z]$个0，即有$forall mn(s)le xle mn(s)+z,(x,s)$合法
类似地，也可以得到$forall mx(s)-zle xle mx(s),(x,s)$合法
由引理即有$mx(s)-mn(s)le 2z-2$，因此两者区间相交，也即得证
由此，问题即$forall s$求$mn(s)$和$mx(s)$，这个问题可以dp解决
具体的，（以$mn(s)$为例）令$f_{s}$为对应的答案，则$f_{s}=min(f_{s},f_{s-a_{i}}+1)$
进一步的，将其对每一种物品（指相同的$a_{i}$）一起处理，假设有$x$个$a_{i}=k$，枚举$s$上选择的$k$个数，即可得到转移为$f_{s}=min_{0le ile x}(f_{s-ik}+i)$，不难用优先队列$o(1)$求出后者
注意到物品种类数至多为$sqrt{n}$，因此总复杂度为$o(nsqrt{n})$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define ll long long 5 int n,x,y,l,r,a[N],tot[N],q[N],mx[N],mn[N],f[N]; 6 ll ans; 7 int main(){ 8 scanf("%d",&n); 9 memset(a,-1,sizeof(a)); 10 for(int i=1;i<n;i++){ 11 scanf("%d%d",&x,&y); 12 a[x]++,a[y]++; 13 } 14 for(int i=1;i<=n;i++)tot[a[i]]++; 15 memset(mn,0x3f,sizeof(mn)); 16 memset(mx,-0x3f,sizeof(mx)); 17 mn[0]=0,mx[0]=tot[0]; 18 for(int i=1;i<=n;i++){ 19 if (!tot[i])continue; 20 for(int j=0;j<i;j++){ 21 l=1,r=0; 22 for(int k=j;k<=n;k+=i){ 23 while ((l<=r)&&(mn[k]-k/i<=mn[q[r]]-q[r]/i))r--; 24 q[++r]=k; 25 while ((l<=r)&&(q[l]/i<k/i-tot[i]))l++; 26 f[k]=mn[q[l]]+(k-q[l])/i; 27 } 28 } 29 memcpy(mn,f,sizeof(f)); 30 } 31 for(int i=1;i<=n;i++){ 32 if (!tot[i])continue; 33 for(int j=0;j<i;j++){ 34 l=1,r=0; 35 for(int k=j;k<=n;k+=i){ 36 while ((l<=r)&&(mx[k]-k/i>=mx[q[r]]-q[r]/i))r--; 37 q[++r]=k; 38 while ((l<=r)&&(q[l]/i<k/i-tot[i]))l++; 39 f[k]=mx[q[l]]+(k-q[l])/i; 40 } 41 } 42 memcpy(mx,f,sizeof(f)); 43 } 44 for(int i=0;i<=n;i++)ans+=max(mx[i]-mn[i]+1,0); 45 printf("%lld ",ans); 46 return 0; 47 }
View Code
Wow, fantastic weblog format! How lengthy have you been blogging for?
you make running a blog look easy. The overall look of your web site is excellent,
as smartly as the content! You can see similar here sklep