题解：AT_abc397_e [ABC397E] Path Decomposition of a Tree
赛时死因：
首先因为找的是路径，所以对于每个叶子节点，它一定会是某条路径的端点之一。
那么考虑类似拓扑排序，对每个叶子节点，即度数为一的点入队，然后可以想象成将一个点合并到与它相连的点，并记录下到这个点的路径长度。
对于一条完整的路径，想象把它删除，因为它的一端是叶子节点，那么只需将另一端点相连的点度数减一，如果成为新的叶子节点就再入队。
大体思路是这样，然后有以下细节需要在遍历时判断：
-
如果新遍历的一个点，它已经属于一条完整的路径，那么说明两条路径存在交叉，显然不行。
-
如果是两个非叶子节点合并后，它们仍未构成一条完整路径，说明这会是一条三叉“路径”，显然不行。
-
最后，一定特判
k=1 !
代码：
#include<bits/stdc++.h>
using namespace std;
vector<int> g[200005];
bool f;
int n,k,d[200005],a[200005],vis[200005];
queue<int> q;
int main()
{
cin>>n>>k;
for(int i=1;i<n*k;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
d[u]++,d[v]++;
}
if(k==1)
{
cout<<"Yes";
return 0;
}
for(int i=1;i<=n*k;i++)
{
a[i]=1;
if(d[i]==1)
q.push(i);
}
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=1;
for(int v:g[u])
{
if(vis[v])
continue;
if(!a[u])
{
d[v]--;
if(d[v]==1)
q.push(v);
break;
}
d[v]--;
if(!a[v])
{
cout<<"No";
return 0;
}
if(a[v]!=1)
{
a[v]+=a[u];
if(a[v]!=k)
{
cout<<"No";
return 0;
}
a[v]=0;
}
else
a[v]+=a[u];
if(a[v]==k)
a[v]=0;
if(d[v]==1)
q.push(v);
break;
}
}
cout<<"Yes";
return 0;
}