专栏文章

题解：P13680 [IAMOI R2] 未送出的花

哈哈哈人生
P13680题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miod7a0p
此快照首次捕获于
2025/12/02 17:17
3 个月前
此快照最后确认于
2025/12/02 17:17
3 个月前
查看原文

题外话

看到题目描述觉得不对劲，再细看题目背景，咦？

思路

首先有个显然的结论，每个节点的盛开度小于其父节点的盛开度一定不劣。因为如果不然，就可以将两个结点调换位置，此时一定不会有节点的美丽值减少还有可能增加。
因此，我们发现将一个深度为 xx 的节点 ii 的盛开度设为 yy，那么其子树内所有深度为 2×x−12\times x-1 和 2×x2\times x 的点 jj 的美丽值必然为 yy。因为一条链上的美丽度是递减的嘛。设 aia_i 为满足条件的 jj 的个数。
考虑到每个节点的盛开度小于其父节点的盛开度的限制，我们从 nn 到 11 来填数。nn 一定要填在 11，之后每个数一定要填在与已填点直接相连的点。假设已经填完了 xx 个数，所有已填点的 aia_i 相加为 yy，那么就表明折下不大于 yy 朵花的美丽值不少于 n−x+1n-x+1。
反着定义动态规划状态，这个就是树上背包了。设 dpijdp_{i_j} 表示以 ii 为根的子树内选了 jj 个点来填（根必填）所有点的 aia_i 之和最多为多少。最后对于每一个 kk，查询最小的 dp1,mdp_{1,m} 使 dp1,m≥kdp_{1,m}\ge k，输出 n−m+1n-m+1 即可。

代码

代码运行时间细节 2626 毫秒。
评测记录。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef int type;
inline type read(){
	type x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(type x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x / 10);
	putchar(x%10+'0');
}
int t,n,dep[10005],f[10005],a[10005],si[100005];
vector<int> v[10005],dp[10005];
void dfs(int p,int fa){
	dep[p]=dep[fa]+1,f[p]=fa;
	for(int i=0;i<v[p].size();i++){
		if(v[p][i]!=fa)dfs(v[p][i],p);
	}
}
int qiu(int p,int fa,int x,int y){
	int ret=0;
	if(dep[p]==x||dep[p]==y)ret++;
	else if(dep[p]>x&&dep[p]>y)return ret;
	for(int i=0;i<v[p].size();i++){
		if(v[p][i]!=fa)ret+=qiu(v[p][i],p,x,y);
	}
	return ret;
}
void cha(int p,int fa){
	si[p]=1;
	dp[p].push_back(0),dp[p].push_back(a[p]);
	for(int i=0;i<v[p].size();i++){
		if(v[p][i]!=fa){
			cha(v[p][i],p);
			while(dp[p].size()<=si[p]+si[v[p][i]])dp[p].push_back(0);
			for(int j=si[p];j>=1;j--){
				for(int k=0;k<=si[v[p][i]];k++){
					dp[p][j+k]=max(dp[p][j+k],dp[p][j]+dp[v[p][i]][k]);
				}
			}
			si[p]+=si[v[p][i]];
		}
	}
}
signed main() {
	t=read();
	while(t--){
		n=read();
		for(int i=1;i<=n-1;i++){
			int x,y;
			x=read(),y=read();
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(1,0);
		for(int i=1;i<=n;i++)a[i]=qiu(i,f[i],dep[i]*2-1,dep[i]*2);
		cha(1,0);
		for(int i=1;i<=n;i++){
			int l=1,r=n,mid,ret;
			while(l<=r){
				mid=(l+r)/2;
				if(dp[1][mid]>=i)ret=mid,r=mid-1;
				else l=mid+1;
			}
			write(n-ret+1),putchar(' ');
		}
		putchar('\n');
		for(int i=1;i<=n;i++)v[i].clear(),dp[i].clear();
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...