[CoE R5] So What Do We Do Now?

Luogu
IDLGP8578
Time1500ms
Memory256MB
DifficultyP3
搜索洛谷原创Special JudgeO2优化构造洛谷月赛
给定一棵 $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$ 取到最小值的点权。 ## Input 第一行一个正整数 $n$ 表示树的结点数。 接下来 $n-1$ 行,每行两个正整数 $u,v$,表示 $u,v$ 之间有一条边。 ## Output 第一行一个 $1,2,\dots,n$ 的排列,表示结点 $1,2,\dots,n$ 的点权。由于赋点权的方式可能有很多种,你只需要输出其中任意一种即可。 [samples] ## Background ![396ac9d3c58dbf329d6ead206944a5a495930006.jpg](https://img-kysic-1258722770.file.myqcloud.com/f2a3112865eea75d3c27aae713e1a8a8/ae2c3e0c34910.jpg) >$\texttt{I'm getting tired of hiding.}$ 声明:上述图片取自网络,`pid:6544352`,如有侵权,告知即删。 ## Note **样例说明** 输入 $\#1$ ![graph.png](https://img-kysic-1258722770.file.myqcloud.com/4a372f1ae46e27a31fae60c4db5e439e/af9581fa182de.png) $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$。
Samples
Input #1
3
1 2
1 3
Output #1
1 2 3
Input #2
2
1 2
Output #2
1 2
Input #3
5
1 2
2 3
3 4
4 5
Output #3
1 2 3 4 5
API Response (JSON)
{
  "problem": {
    "name": "[CoE R5] So What Do We Do Now?",
    "description": {
      "content": "给定一棵 $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",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8578"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一棵 $n$ 个结点的有根树,根结点编号为 $1$。设以 $i$ 为根的子树为 $T_i$。你需要给每个结点赋一个正整数点权 $v_i$,使得所有点的点权恰为 $1,2,\\dots,n$ 各一个。记\n$$f=\\sum_{i=1}^{n}R_i,$$\n其中 $R_i$ 是以 $i$ 为根的子树中点权的极差,即\n$$R_i=\\max_{j \\in T_i}\\{v_j\\}-\\min_{j \\in T...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments