Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov! F——Nastya and Time Machine dfs+构造

参考博客:https://blog.csdn.net/qq_45458915/article/details/105730195
构造nb

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=2e5+100;
vector<int>node[N];
vector<pair<int,int>>ans;
int mmax;
//1 -1 0
void dfs(int u,int fa,int t)//在区间 [ mmax - son - 1 , mmax ] 内赋值
{
	int temp=t;
	//					1 0
	//从父节点下来 
	ans.push_back(make_pair(u,t));
	int son=node[u].size()-(u!=1);//有多少个子节点
	for(auto v:node[u])
	{
		if(v==fa)
			continue;
		if(t==mmax)//如果已经到最大值了,那么切换成最小值
		{
			t=mmax-son-1;
			ans.push_back(make_pair(u,t));
		}
		t++;
		//去递归子节点 
		dfs(v,u,t);
		//从子节点上来 
		ans.push_back(make_pair(u,t));
	}
	//当到达叶节点的时候,通过上面的进入ans
	//然后上面的for循环由于遇到 v==fa 且就执行一次
	//所以直接到下面,相当于叶节点回溯 
	//只有是叶节点 的时候 才会执行 
	
	//对于节点2来说
	//temp保存的是从父节点进入到的时间
	//此时的t是遍历完子节点上来的时间 
	if(u!=1&&t!=temp-1)
		ans.push_back(make_pair(u,temp-1));
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1; i<n; i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		node[u].push_back(v);
		node[v].push_back(u);
	}
	for(int i=1; i<=n; i++)
		mmax=max(mmax,(int)node[i].size());
	dfs(1,-1,0);
	printf("%d\n",ans.size());
	for(int i=0; i<ans.size(); i++)
		printf("%d %d\n",ans[i].first,ans[i].second);
	return 0;
}

Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov! F——Nastya and Time Machine dfs+构造

上一篇:Archlinux Gnome下ibus


下一篇:Linux基础-Crond服务