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

赛时死因：

k=1

。

首先因为找的是路径，所以对于每个叶子节点，它一定会是某条路径的端点之一。

那么考虑类似拓扑排序，对每个叶子节点，即度数为一的点入队，然后可以想象成将一个点合并到与它相连的点，并记录下到这个点的路径长度。

对于一条完整的路径，想象把它删除，因为它的一端是叶子节点，那么只需将另一端点相连的点度数减一，如果成为新的叶子节点就再入队。

大体思路是这样，然后有以下细节需要在遍历时判断：

如果新遍历的一个点，它已经属于一条完整的路径，那么说明两条路径存在交叉，显然不行。
如果是两个非叶子节点合并后，它们仍未构成一条完整路径，说明这会是一条三叉“路径”，显然不行。
最后，一定特判 $k=1$ !

代码：

CPP

	#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;
	}

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

文章操作

相关推荐

评论

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