526互联

Codeforces Round 866 (Div. 1) C. The Fox and the Complete Tree Traversal （构造）

发布时间 2023-04-27 11:22:19作者: qdhys

传送门

题目大意：

  给定一个有n个点的树，我们可以任意选择一个点作为起点，这个点可以跳到跟自己距离为1或者距离为2的点，已经到达的点不能再到达（最终必须回到起点），询问是否存在一种方案可以从一个点出发经过所有的点最终再回到这个点来。

  输入一个整数n。紧接着输入n-1条边。

大致思路：

  我们会发现我们在走一个树链的时候，如果树链上挂着一个深度大于等于2的点就会无解，所以我看考虑找到一个最长的树链，也就是树的直径。我们可以发现这么一个构造方案：找到树的直径，然后从一端往另一端走，每次跳到奇数点回来的时候走偶数点，最终回到起点。我们会发现如果树的直径上挂了一个深度大于等于二的点就会无解。否则一定有解。对于树直径上挂的深度为1的点就是去的时候把偶数点的所有子树跳完再去偶数点，回来的时候把奇数点的子树跳完再去偶数点回到起点即可。

#include <bits/stdc++.h>

const int N = 2e5 + 10;
const int M = 1e5 + 10;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef std::pair<int, int> PII;
int n, m;

int h[N], ne[N << 1], e[N << 1], idx;
int fa[N], nxt[N];

inline void add(int a, int b) {
	ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}

int dep[N], mx, id;
bool used[N];
bool vis[N];

bool ok = true;

inline void dfs1(int u, int father, int depth) {
	dep[u] = depth;
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == father)	continue;
		dfs1(j, u, depth + 1);
	}
	
	if (depth > mx) {
		mx = depth;
		id = u;
	}
}

inline void dfs2(int u, int father, int depth) {
	dep[u] = depth;
	fa[u] = father;

	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == father) continue;
		dfs2(j, u, depth + 1);
	}
	
	if (depth > mx) {
		mx = depth;
		id = u;
	}
}

inline bool dfs(int u, int fa, int sz) {
	if (sz == 2)	return false;
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == fa || vis[j]) continue;
		if (!dfs(j, u, sz + 1))	return false;
	}
	return true;
}

inline void solve(){
	std::cin >> n;
	memset(h, -1, sizeof h);
	for (int i = 0; i < n - 1; i ++) {
		int a, b;
		std::cin >> a >> b;
		a --, b --;
		add(a, b);
		add(b, a);
	}
	
	dfs1(0, -1, 1);
	int id1 = id;
	id = mx = 0;

	dfs2(id1, -1, 1);
		
	int now = id, last = id;
	while (now != -1) {
		vis[now] = true;
		if  (fa[now] != -1)
		nxt[fa[now]] = now;
		if (fa[now] == -1)	last = now;
		now = fa[now];
	}
	
	for (int i = id; ~i; i = fa[i]) {
		if (!dfs(i, -1, 0)) {
			std::cout << "No" << '\n';
			return ;
		}
	}
	
	std::vector<int> ans;
	
	auto get = [&](int u) -> void {
		for (int i = h[u]; ~i; i = ne[i]) {
			int j = e[i];
			if (vis[j])	continue;
			if (used[j]) continue;
			ans.push_back(j);
			used[j] = true;
		}
	};
	
	std::cout << "Yes" << '\n';
	for (int i = id; ~i; i = fa[i]) {
		used[i] = true;
		ans.push_back(i);
		i = fa[i];
		get(i);
		if (i == -1)	break;
	}
	
	 for (int i = last; i != id; i = nxt[i]) {
	 	get(i);
	 	if (!used[i]) ans.push_back(i);
	 }
	 get(id);
	
	for (auto &v: ans)	std::cout << v + 1<< ' ';
	std::cout << '\n';
}

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int _;
	_ = 1;
	//std::cin >> _;
	
	while (_ --) solve();
	
	return 0;
}