[Codeforces] CF1675D Vertical Paths

题目描述

给定一棵由 \(n\) 个顶点组成的有根树。顶点由 \(1\) 到 \(n\) 编号。任何顶点都可以是树的根。

请在树上找出这样一组路径：

• 每个顶点恰好属于一条路径，每条路径可以包含一个或多个顶点；
• 在每条路径中，每个节点的下一个节点是当前节点的子节点（即路径总是向下 —— 从父节点到子节点）；
• 路径的数量最少。

思路

很明显，任何一棵树，如果我们按照其深度优先遍历的顺序分段（每次向后退时分一段），那么得到的一定是最小的路径数量。

为什么呢？想象一下，假如我们到达了一个节点，他有三个子节点，无论选哪个，路径都最少会分出三个叉来

所以，这道题就成了一道深搜

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int n,cnt,root;
int p[Maxn];
vector<int>node[Maxn];
vector<int>ans[Maxn];
void find(int now)
{
	ans[cnt].push_back(now);
	if(node[now].size()==0)
	{
		cnt++;
		return ;
	}
	for(int i=0;i<node[now].size();i++) find(node[now][i]);
}
void run()
{
	cin>>n;cnt=0;
	vector<int>t;
	for(int i=0;i<=n+1;i++) ans[i]=t,node[i]=t;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i];
		if(p[i]==i) root=i;
		else 
		{
			node[p[i]].push_back(i);
		}
	}
	find(root);
	cout<<cnt<<endl;
	for(int i=0;i<cnt;i++)
	{
		cout<<ans[i].size()<<endl;
		for(int j=0;j<ans[i].size();j++)
		{
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) run();
}