思路

考虑盛开度已经确定后，对于一个点

u

到点

1

路径上两个节点盛开度

x,y(x<y)

，交换此处两盛开度对于点

u

的美丽度没有影响，同时如果

x

的节点比

y

的节点高，交换它们一定不劣。

同上，考虑一种情况，盛开度

x

的位置到盛开度

y

父节点间有任意分支，交换

x,y

后，这些分支上的点到点

1

路径上点的盛开度集合中的一个元素被替换为一个更大的数，同时盛开度

y

的点及其子树内不受影响。

于是有性质，父节点盛开度大于子节点盛开度更优。据此，如果一个节点深度为

d

，那么它的美丽度由它到点

1

路径上深度为

\lceil\frac{d}{2}\rceil

的节点的盛开度确定。

我们可以知道每个点的盛开度确定多少个点的美丽度，题目相当于求与点

1

相连最小联通块满足美丽度确定点的个数大于等于

k

。

树上背包即可，令

f_{u,i}

表示

u

子树内包含

u

的大小

i

的联通块美丽度确定点数最大值，转移显然：

\large f_{fa_u,i+j}=\max(f_{fa_u,i+j},f_{fa_u,i}+f_{u,j})

code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,p[N],siz[N],son[N],F[N],f[N][N];
int head[N],vi[N<<1],nxt[N<<1],tot;
inline void add(int u,int v){
	vi[++tot]=v;nxt[tot]=head[u];head[u]=tot;
	vi[++tot]=u;nxt[tot]=head[v];head[v]=tot;
	return;
}
inline void dfs(int u,int fa,int dep){
	p[dep]=u;
	son[p[dep/2]]++;
	for(int i=head[u];i;i=nxt[i]){
		int v=vi[i];
		if(v==fa)continue;
		dfs(v,u,dep+1);
	}
	return;
}
inline void dp(int u,int fa){
	siz[u]=1;
	f[u][1]=son[u];
	for(int i=head[u];i;i=nxt[i]){
		int v=vi[i];
		if(v==fa)continue;
		dp(v,u);
		for(int j=siz[u]+siz[v];j>siz[u];j--)f[u][j]=0;
		for(int j=1;j<=siz[u];j++)F[j]=f[u][j];
		for(int j=1;j<=siz[u];j++)
		for(int k=1;k<=siz[v];k++)
			f[u][j+k]=max(f[u][j+k],F[j]+f[v][k]);
		siz[u]+=siz[v];
	}
}
inline void solve(){
	n=read();
	tot=0;
	for(int i=1;i<=n;i++)
		head[i]=son[i]=0;
	for(int i=1;i<n;i++)add(read(),read());
	dfs(1,0,0);
	dp(1,0);
	for(int i=1;i<=siz[1];i++)
	for(int j=f[1][i-1]+1;j<=f[1][i];j++)
		printf("%d ",n-i+1);
	puts("");
	return;
}
int main(){
//	freopen("c.in","r",stdin);
//	freopen("c.out","w",stdout);
	int t=read();
	while(t--)solve();
	return 0;
}

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

文章操作

思路

code

相关推荐

评论

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