ARC175D LIS on Tree 2

发表于 分类于 本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

给一棵 个节点的树，将 的排列填入节点内，使得根节点到每个节点的简单路径的权值 LIS 长度和为 ，给出构造。

思路

根据 LIS 的性质有：

只要 满足上述条件，就一定存在一种构造使其满足对应 的值。

我们首先令 取其下界，即 。

然后考虑令 会产生什么影响。不难发现，此时 子树内所有节点的下界都必须加一，即 必须加 的子树大小。

现在问题变为，我们可以选择一些子树，使其内 都加一，使得 。

直接按子树大小排序，然后贪心能选就选。

我们现在求出了 ，考虑怎么按其进行构造。

对于节点 ，为了使其前面有足够多比其权值小的数，以此凑够 ，所以 越大 也应该越大。

按 升序排序，依次填入 即可。

有一个细节，在 相等的一个连通块内，为了不让较深节点的 变大，则应使得 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
const int N = 2e5+10;
int n,dtop; ll k;
struct{
	int to,nex;
}edge[N<<1];
int head[N],edge_num;
inline void add(int x,int y){
	edge[++edge_num].to = y;
	edge[edge_num].nex = head[x];
	head[x] = edge_num;
}
struct node{
	int siz,pos;
	inline int operator < (const node&G) const{
		return siz < G.siz;
	}
}g[N];
inline void dfs1(int now,int fu){
	g[now] = {1,now};
	for(int i=head[now];i;i=edge[i].nex){
		int tto = edge[i].to;
		if(tto==fu) continue;
		dfs1(tto,now);
		g[now].siz += g[tto].siz;
	}
}
struct WP{
	int L,pos,dfn;
	inline int operator < (const WP&G){
		if(L^G.L) return L > G.L;
		return dfn < G.dfn;
	}
}wp[N];
inline void dfs2(int now,int fu){
	wp[now].L += wp[fu].L;
	wp[now].pos = now;
	wp[now].dfn = ++dtop;
	for(int i=head[now];i;i=edge[i].nex){
		int tto = edge[i].to;
		if(tto==fu) continue;
		dfs2(tto,now);
	}
}
int ans[N];
int main(){

	read(n,k);
	if(k<n){
		puts("No");
		return 0;
	}
	for(int i=1,u,v;i<n;++i){
		read(u,v);
		add(u,v);
		add(v,u);
	}
	dfs1(1,0);
	sort(g+1,g+1+n); // 按子树大小排序之后贪心
	for(int i=n;i && k;--i){
		if(k>=g[i].siz){
			k -= g[i].siz;
			++wp[g[i].pos].L; // 对 L 差分
		}
	}
	if(k){ // 所有子树都选了还是到不了 K
		puts("No");
		return 0;
	}
	dfs2(1,0);
	sort(wp+1,wp+1+n);// 按 L 排序和 dfn 排序
	for(int i=1;i<=n;++i) ans[wp[i].pos] = n-i+1;
	puts("Yes");
	for(int i=1;i<=n;++i) printf("%d ",ans[i]);

	return 0;
}