自动搬运

查看原文

来自洛谷，原作者为

	Da_un Rome was not built in a day

搬运于2025-08-24 22:40:21，当前版本为作者最后更新于2022-10-17 18:56:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

求 $f=\sum\limits_{i=1}^n R_i$ 中的 $f_{min}$，只需让每个 $R_i$ 尽可能地小就行了，即让每个以 $i$ 为根的子树中点权的极差最小，这需要在某种遍历时给点附上权值来实现。

这种遍历的应该尽可能的让父亲与儿子的权值相邻，不断遍历，不断赋值，由局部最优推到全局最优，讲到这里，大家应该也都明白了其实这就是深搜遍历，也叫作 dfs 序。

dfs 序是指每个节点在 dfs 深度优先遍历中的进出栈的时间序列，我们把树建完跑一遍 dfs 序，dfs 进入子树 $i$ 的时间就是每个点应附的权值。因为根节点未给出，我们可以任选一个作为根节点，最后输出进入的时间戳即为答案。

Code

#include<iostream>
#include<cstdio> 
#include<vector>
#include<algorithm>
using namespace std;
const int N=1000100;
int n;
int in[N],out[N];
int u,v;
int Times;
vector<int> f[N];
void dfs(int now,int fa)
{
	in[now]=++Times;//dfs进入now的时间
	for(int i=0;i<f[now].size();i++)
		if(f[now][i]!=fa) dfs(f[now][i],now);
	//out[now]=Times;//dfs离开子树now的时间，这题用不到
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		f[u].push_back(v);
		f[v].push_back(u);
	}
	dfs(1,0);//选1为根节点
	for(int i=1;i<=n;i++)	
		printf("%d ",in[i]);
	return 0;
}