題目描述

給一棵 \(n\) 個節點的樹，將 \(1 \sim n\) 的排列填入節點內，使得根節點到每個節點的簡單路徑的權值 LIS 長度和為 \(K\)，給出構造。

思路

根據 LIS 的性質有：

• \(L_1 = 1\)
• \(L_{fa_u} \le L_u \le L_{fa_u}+1\)

只要 \(L\) 滿足上述條件，就一定存在一種構造使其滿足對應 \(L\) 的值。

我們首先令 \(L\) 取其下界，即 \(\forall i,L_i = L_{fa_i}\)。

然后考慮令 \(L_u = L_{fa_u}+1\) 會產生什么影響。不難發現，此時 \(u\) 子樹內所有節點的下界都必須加一，即 \(\sum L_i\) 必須加 \(u\) 的子樹大小。

現在問題變為，我們可以選擇一些子樹，使其內 \(L\) 都加一，使得 \(\sum L_i = K\)。

直接按子樹大小排序，然后貪心能選就選。

我們現在求出了 \(L\) ，考慮怎么按其進行構造。

對于節點 \(u\)，為了使其前面有足夠多比其權值小的數，以此湊夠 \(L_u\)，所以 \(L_u\) 越大 \(v_u\) 也應該越大。

按 \(L\) 升序排序，依次填入 \(n \sim 1\) 即可。

有一個細節，在 \(L\) 相等的一個連通塊內，為了不讓較深節點的 \(L_u\) 變大，則應使得 \(v_{fa_u} > v_u\)。

代碼

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;
}