题意

给定一棵具有 N*K 个顶点无向树。顶点编号为 1,2,…,N*K-1,,…,N*K （则有N*K-1条边）

确定此树是否可以分解为 N 条路径，每条路径的长度为 K 。

思路

首先我们必须要理解路径的概念， 即如图无分叉的为一条路径

对于样例一，N=3，K=2时，所分割样例如图所示：

对于树的用邻接表存储就不在过多赘述，这里我们主要讨论解题思路。

显而易见，我们需要用dfs来进行搜索，每次对于找到的符合条件的路径返回的符合条件的路径进行一个处理。

那么我们想到在dfs里用变量cnt记录到此结点的子树中的路径数，sum记录到此结点的子树中总的节点数。

因为没有指定根节点，我们直接从节点1开始搜索，每次递归进入子节点时，遍历这个子节点的子节点，那么如果进行判断呢？

我们想到由于是无向图，我们在遍历时会处理到这个子节点和父节点之间的边，所以此时不能需要跳过。如果此节点的子树中分叉超过2，即cnt>2，那么一定无法形成合法路径，那么直接返回-1，此时如果sum统计的子树节点数（此时不包含此结点）sum = K-1， 那么意味着形成了合法路径，则可以返回0（代表下面没有不在合法路径的节点需要处理了）， 相当于动态规划处理掉了这条路径，而注意，下面我们还需要对cnt=2进行判断，因为当cnt=2时存在以下情况：

但是如果不符合sum = K-1，也就意味着不可能如图所示存在合法路径， 那么就无法形成合法路径，需要返回-1。

除去以上情况，就只可能是存在节点数还不够成为合法路径的情况了， 那么我们只需要返回sum+1（加上当前节点）。

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

int N, K;
vector<vector<int>> edge;

int dfs(int x, int p = -1)
{
	
	int cnt = 0;
	int sum = 0;
	for(auto y : edge[x])
	{
		if(y == p) continue;
		int t = dfs(y, x);
		if(t == -1) return -1;
		else if(t > 0)
		{
			cnt ++;
			sum += t;
		}
	}
	
	if(cnt > 2) return -1;
	else if(sum == K - 1) return 0;
	else if(cnt == 2) return -1;
	else return sum + 1;
}

signed main()
{
	cin >> N >> K;
	//cout << N << ' ' << K << endl;
	edge.resize(N*K);
	for(int i = 1, u, v; i < N*K; ++ i)
	{
		cin >> u >> v;
		u --, v --;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	
	if(dfs(0) == 0) cout << "Yes" << endl;
	else cout << "No" << endl;
}