本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-08 09:46:08

构造题，dfs序可以使得差值最小。

#include<bits\/stdc++.h>
using namespace std;
const int N=1e6+9;
vector<int>t[N];
int n,dfn[N],u,v;
long long ans;
void dfs(int u,int fa){
	dfn[u]=++id;
	for(auto v:t[u]){
		if(v==fa)continue;
		dfs(v,u);
	}	
}

int main(){
	memset(din,63,sizeof(din));
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		t[u].push_back(v) ;
		t[v].push_back(u);	
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)cout<<dfn[i]<<" ";
}