ABC397E题解

考虑对于每一个结点，有三种可能：

和自己的其中一个子节点连为一条链。
和自己的两个子节点连为一条链，自己为链中间的一个结点。
自己所有子节点都可以独自构成一条长为 $K$ 的链，自己和父节点连为一条链。

不难发现，所有子节点构成的链的长度中最多只有两条不为

K

。当有一条时，可以将当前结点接到这个链上；当有两条时，可以将这两条一左一右和当前结点拼接，即当前结点为这条链中间的一个点，然后计算这个长度，若不为

K

则输出 No。
我们设计一个 dfs 函数，它的返回值为以这个点为端点的链的长度。及只有在第

1

和第

3

种情况时才会返回这个长度，当为第

2

种情况时，返回

0

。当不满足情况，即要输出 No 时，返回

-1

。
那么我们只需要在 dfs 过程中开一个数组记录一下每个 dfs 的返回值，然后再数一下数组中有多少个值不为

K

，再跟上一个判断就行了。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5+5;

int n, k;
vector<int> e[MAXN];

int dfs(int u, int fa)
{
	vector<int> siz;
	for(int i = e[u].size()-1;i >= 0;i--)
	{
		int v = e[u][i];
		if(v == fa) continue;
		int sz = dfs(v, u);
		if(sz) siz.push_back(sz);
		if(sz == -1) return -1;
	}
	int cnt = 0;
	int re = 0;
	vector<int> sta;//存的是长度不为 K 的链的长度
	for(int i = siz.size()-1;i >= 0;i--)
	{
		int sz = siz[i];
		if(sz != k)
		{
			sta.push_back(sz);
		}
	}
	if(sta.size() > 2)
	{
		return -1;
	}
	if(sta.size() == 1)
	{
		return sta[0]+1;
	}
	if(sta.size() == 2)
	{
		if(sta[0] + sta[1] + 1 != k) return -1;
		else return 0;
	}
	return 1;
  //最后记得要return 1（我就是这个 1 打成 0 了赛后4min才调出来）
}

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

文章操作

相关推荐

评论

ABC397E题解