题解：AT_abc397_e [ABC397E] Path Decomposition of a Tree

题目传送门：洛谷 AtCoder

闲话

赛时差点切掉，都怪D题太烦了，我还是太弱了

思路

考虑一般情况，我们要怎么走才能最优呢？随便画一棵树，当且仅当

K = 3

，然后就能得到下面的图：

不难发现每次走就像是从下往上找更优，我们再具体看一下，现在给每个节点表上序号：

还是

K = 3

的情况，看到编号为 2 的节点，它有三个子树，分别为 4、5、6，每个子树要么就是分完了，像节点 4、5 一样，恰好有 K 的倍数个儿子节点，所以分完了。否则的话，它就可能有那么一条升上来的链，它的长度一定小于 K ，因为多的你就直接给它分掉就行了。比如你一个子树它有若干条链没有分完，那如果剩下的拼在一起已经不是一个链了，那它就直接无解了。

比如下面的情况，还是

K = 3

的情况：

此时看到编号为 2 的节点，它的三个子树分别再分完后还剩下 5、6、7 三个子节点，但他们已经不是一条链了，所以我们又能发现：一个节点最多允许两个不同的子树剩余，否则形成不了链，无解。

既然剩余不同子树数量大于 2 无解，那如果小于等于 2 又是怎样呢？

剩余不同子树数量等于二的情况：

多出来的两个只能和他们的父亲节点形成链，所以只有两个子树剩余子节点的数量再加上父亲节点 1 等于 K 才算有解。
剩余不同子树数量等于一的情况：

先把这个子树的子节点数量再加上父亲节点 1 看看还能不能再找出长度为 K 的路径，如果还剩了，就再往上看。
没有剩余的子树

那就只有自己一个节点 1，继续往上看。

思路没问题了，那该怎么实现呢？如果真的按照思路那样从下往上看的话代码会很难写，其实只用从上往下 dfs 一遍，每次返回还剩多少。对当前的某个节点的子节点 dfs，把值存在一个 vector 里，如果像思路里那样数量超过了二就输出 No 然后 exit；数量等于二就看两个子树剩余子节点数量加上父亲节点 1 是否等于 K，不等于就输出 No 然后 exit，否则就 return 0 表示没有剩余的了；数量等于一就把那个子树剩余子节点数量加上父亲节点 1 去模 K 看一看还剩多少然后 return 回去；否则就说明没有剩余的了，直接把这个节点 1 给 return 就行啦。

Code

思路里讲的很清楚了，代码就不具体解释啦。

CPP

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> edge[200001];

int dfs(int x, int fa) {
	vector<int> c;
	for (auto i : edge[x]) {
		if (i == fa)
			continue;
		int y = dfs(i, x);
		if (y > 0)
			c.push_back(y);
	}
	if (c.size() >= 3) {
		printf("No");
		exit(0);
	}
	else if (c.size() == 2) {
		if (c[0] + c[1] + 1 != k) {
			printf("No");
			exit(0);
		}
		return 0;
	}
	else if (c.size() == 1)
		return (c[0] + 1) % k;
	return 1;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i < n * k; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	if (k == 1) {
		printf("Yes");
		return 0;
	}
	printf(!dfs(1, 0) ? "Yes" : "No");
}

完美散花！o((>ω< ))o

题解：AT_abc397_e [ABC397E] Path Decomposition of a Tree

文章操作

闲话

思路

Code

相关推荐

评论

题解：AT_abc397_e [ABC397E] Path Decomposition of a Tree