CF1311E 题解

题意: 构造一个节点数为 \(n\) 的树, 使得节点深度之和为 \(d\). (根节点为 \(1\) 且深度为 \(0\))

显然, 不断构造二叉树并检查是否为答案是行不通的, 只能在 \(O(n)\) 的时间内构造, 不然就T了.

我们可以轻易得出构造的二叉树节点深度和最大是一条链的情况, 最小是满二叉树. 这道题, 我们可以由满二叉树转移至目标树.

考虑暴力的方法, 我们可以每次使总和加一, 只需将一个节点向下移即可. 为了保证其始终是一棵二叉树, 我们应该使节点尽量往左靠且尽可能能往下移使其构成一条链.

#include<cstdio>
#include<cmath>

#define Maxn 10000

using namespace std;

int T, n, d, fa[Maxn + 9], dep[Maxn + 9], id[Maxn + 9], deepest;
bool _true[Maxn + 9];

int read() {
	int sum = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') sum = (sum << 3) + (sum << 1) + ch - '0', ch = getchar();
	return sum * f;
}

void write(int x) {
	if(x < 0) putchar('-'), write(-x);
	else if(x <= 9) putchar(x + '0');
	else write(x / 10), putchar(x % 10 + '0');
}

void Run() {
	n = read(), d = read();
	int need = d;
	for(int i = 1; i <= n; ++i) {
		_true[i] = 0;
		need -= dep[i];
		int leftson = i << 1, rightson = i << 1 | 1;
		if(leftson <= n) fa[leftson] = i, dep[leftson] = dep[i] + 1;
		if(rightson <= n) fa[rightson] = i, dep[rightson] = dep[i] + 1;
	}
	if(need < 0 || d > (n - 1) * n / 2) {puts("NO"); return;}
   	puts("YES");
	int now = 1;
	while(now <= n) _true[now] = 1, id[dep[now]] = now, now = now << 1;
	deepest = log2(n);
	for(int i = n; i >= 1 && need; --i) {
		if(_true[i]) continue;
		while(need) {
			--need;
			fa[i] = id[dep[i]], dep[i] = dep[fa[i]] + 1;
			if(dep[i] > deepest) {deepest = dep[i], id[dep[i]] = i; break;}
		}
		
		_true[i] = 1;
	}
	for(int i = 2; i <= n; ++i) write(fa[i]), putchar(' ');
	puts("");
}

signed main() {
	T = read();
	while(T--) {
		Run();
	}
	return 0;
}

显然, 这样达不到 \(O(n)\) 的效率, 观察可得, 我们其实不用一步步移, 如果能移到底端我们应该直接往下移, 否则扔到半路就可以结束了.

#include<cstdio>
#include<cmath>

#define Maxn 10000

using namespace std;

int T, n, d, fa[Maxn + 9], dep[Maxn + 9], id[Maxn + 9], deepest;
bool _true[Maxn + 9];

int read() {
	int sum = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') sum = (sum << 3) + (sum << 1) + ch - '0', ch = getchar();
	return sum * f;
}

void write(int x) {
	if(x < 0) putchar('-'), write(-x);
	else if(x <= 9) putchar(x + '0');
	else write(x / 10), putchar(x % 10 + '0');
}

void Run() {
	n = read(), d = read();
	int need = d;
	for(int i = 1; i <= n; ++i) {
		_true[i] = 0;
		need -= dep[i];
		int leftson = i << 1, rightson = i << 1 | 1;
		if(leftson <= n) fa[leftson] = i, dep[leftson] = dep[i] + 1;
		if(rightson <= n) fa[rightson] = i, dep[rightson] = dep[i] + 1;
	}
	if(need < 0 || d > (n - 1) * n / 2) {puts("NO"); return;}
	puts("YES");
	int now = 1;
	while(now <= n) _true[now] = 1, id[dep[now]] = now, now = now << 1;
	deepest = log2(n);
	for(int i = n; i >= 1 && need; --i) {
		if(_true[i]) continue;
		int w = deepest + 1 - dep[i];
		if(w <= need) need -= w, fa[i] = id[deepest], ++deepest, id[deepest] = i, dep[i] = deepest;
		else fa[i] = id[dep[fa[i]] + need], need = 0, dep[i] += need;
		_true[i] = 1;
	}
	for(int i = 2; i <= n; ++i) write(fa[i]), putchar(' ');
	puts("");
}

signed main() {
	T = read();
	while(T--) {
		Run();
	}
	return 0;
}