[CoE R5] So What Do We Do Now?
题目背景
\(\texttt{I'm getting tired of hiding.}\)
声明：上述图片取自网络，作者不明，如有侵权，告知即删。
题目描述
给定一棵 \(n\) 个结点的有根树，根结点编号为 \(1\)。设以 \(i\) 为根的子树为 \(T_i\)。你需要给每个结点赋一个正整数点权 \(v_i\)，使得所有点的点权恰为 \(1,2,\dots,n\) 各一个。记
\[f=\sum_{i=1}^{n}R_i, \]其中 \(R_i\) 是以 \(i\) 为根的子树中点权的极差，即
\[R_i=\max_{j \in T_i}\{v_j\}-\min_{j \in T_i}\{v_j\}. \]对于所有的赋点权的方式，请求出一组使 \(f\) 取到最小值的点权。
输入格式
第一行一个正整数 \(n\) 表示树的结点数。
接下来 \(n-1\) 行，每行两个正整数 \(u,v\)，表示 \(u,v\) 之间有一条边。
输出格式
第一行一个 \(1,2,\dots,n\) 的排列，表示结点 \(1,2,\dots,n\) 的点权。由于赋点权的方式可能有很多种，你只需要输出其中任意一种即可。
样例 #1
样例输入 #1
3
1 2
1 3
样例输出 #1
1 2 3
样例 #2
样例输入 #2
2
1 2
样例输出 #2
1 2
样例 #3
样例输入 #3
5
1 2
2 3
3 4
4 5
样例输出 #3
1 2 3 4 5
提示
样例说明
输入 \(\#1\)
\(R_1=3-1=2,R_2=2-2=0,R_3=3-3=0,f=R_1+R_2+R_3=2\)，可以证明，不存在使得 \(f\) 更小的构造。
数据范围
对于 \(10\%\) 的数据，\(n \le 10\)；
对于另外 \(10\%\) 的数据，树是一条链；
对于另外 \(20\%\) 的数据，有一个结点与其他 \(n-1\) 个结点都相连；
对于另外 \(20\%\) 的数据，树是一棵完全二叉树，即除了叶子结点外每个结点都恰有两个子结点；
对于 \(100\%\) 的数据，\(1 \le n \le 10^6\)。
思路
树上\(DP\)，先建树，然后遍历整棵树，求出每棵子树的节点数，接着在求出答案，把一棵树拆成几个子树进行求解，这里要注意答案不一定从\(1\)开始存，所以要传一个变量，告诉函数从哪个地方开始存答案。
由于存答案时一棵子树的答案长度和子树大小相等，所以计算每个子树时，每算完一个子树，就要把开始存答案的位置加上子树大小。
然后就没有然后了。
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000010,M = 2 * N;
int n;
int h[N],e[M],ne[M],idx;
int s[N];
int ans[N];
void add (int a,int b) { //链式前向星
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void get_size (int u,int fa) { //这里传入父亲是防止死递归
s[u] = 1;
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (j == fa) continue;
get_size (j,u);
s[u] += s[j]; //加上子树大小
}
}
void dfs (int u,int fa,int add) {
ans[u] = add + 1; //先存答案
int t = add + 1; //要加1，因为当前点已经存了数
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs (j,u,t);
t += s[j]; //到下一个位置
}
}
int main () {
memset (h,-1,sizeof (h));
cin >> n;
for (int i = 1;i <= n - 1;i++) {
int a,b;
cin >> a >> b;
add (a,b),add (b,a);
}
get_size (1,0),dfs (1,0,0);
for (int i = 1;i <= n;i++) cout << ans[i] << ' ';
cout << endl;
return 0;
}