P8578 题解

Da_un · 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;
}