{"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_i}\\{v_j\\}.$$\n对于所有的赋点权的方式，请求出一组使 $f$ 取到最小值的点权。\n\n## Input\n\n第一行一个正整数 $n$ 表示树的结点数。\n\n接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u,v$ 之间有一条边。\n\n## Output\n\n第一行一个 $1,2,\\dots,n$ 的排列，表示结点 $1,2,\\dots,n$ 的点权。由于赋点权的方式可能有很多种，你只需要输出其中任意一种即可。\n\n[samples]\n\n## Background\n\n![396ac9d3c58dbf329d6ead206944a5a495930006.jpg](https://img-kysic-1258722770.file.myqcloud.com/f2a3112865eea75d3c27aae713e1a8a8/ae2c3e0c34910.jpg)\n\n>$\\texttt{I'm getting tired of hiding.}$\n\n声明：上述图片取自网络，`pid:6544352`，如有侵权，告知即删。\n\n## Note\n\n**样例说明**\n\n输入 $\\#1$\n\n![graph.png](https://img-kysic-1258722770.file.myqcloud.com/4a372f1ae46e27a31fae60c4db5e439e/af9581fa182de.png)\n\n$R_1=3-1=2,R_2=2-2=0,R_3=3-3=0,f=R_1+R_2+R_3=2$，可以证明，不存在使得 $f$ 更小的构造。\n\n------------\n\n**数据范围**\n\n对于 $10\\%$ 的数据，$n \\le 10$；\n\n对于另外 $10\\%$ 的数据，树是一条链；\n\n对于另外 $20\\%$ 的数据，有一个结点与其他 $n-1$ 个结点都相连；\n\n对于另外 $20\\%$ 的数据，树是一棵完全二叉树，即除了叶子结点外每个结点都恰有两个子结点；\n\n对于 $100\\%$ 的数据，$1 \\le n \\le 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8578","tags":["搜索","洛谷原创","Special Judge","O2优化","构造","洛谷月赛"],"sample_group":[["3\n1 2\n1 3","1 2 3"],["2\n1 2","1 2"],["5\n1 2\n2 3\n3 4\n4 5","1 2 3 4 5"]],"created_at":"2026-03-03 11:09:25"}}