| 题目名称 | 2125. [HZOI 2015] Tree |
|---|---|
| 输入输出 | hzoi2015tree.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 zys
于2015-12-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：9， 提交：11， 通过率：81.82% | ||||
 核糖核酸 |
100 | 0.928 s | 19.39 MiB | C++ |
 再见 |
100 | 1.464 s | 27.00 MiB | C++ |
 zys |
100 | 1.488 s | 31.19 MiB | C++ |
 000 |
100 | 1.513 s | 57.59 MiB | C++ |
 <蒟蒻>我要喝豆奶 |
100 | 1.529 s | 28.90 MiB | C++ |
 assassain |
100 | 1.530 s | 28.90 MiB | C++ |
|
assassain |
100 | 1.555 s | 28.90 MiB | C++ |
 stdafx.h |
100 | 1.750 s | 43.19 MiB | C++ |
 FoolMike |
100 | 2.187 s | 25.56 MiB | C++ |
|
stdafx.h |
40 | 1.173 s | 27.01 MiB | C++ |
| 关于 Tree 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
                                                                                                     forever
2015-12-19 20:52
1楼
| ||||
【题目描述】
你有一个n个节点的树。现在你有特殊能力，能将树划分成若干条链。
一个有根树的树链剖分为将整棵树划分成若干条从一个点到这个点的祖先（包括本身）的链，并且这些链没有公共点。如果一条边在某条链上，即这条边的两个端点在同一个链上，那么这个边为重边，否则为轻边。
一个树链剖分的代价为所有点对的路径上轻边的个数之和。这里将u,v和v,u当成同一个点对。一个有根树的最优树链剖分为所有方案中代价最小的方式。
你想通过合理地使用你的特殊能力，使得树链剖分最优。
你得到了一个无根树，你想知道以每个点为根对应的有根树的最优树链剖分的代价。
【输入格式】
第一行一个整数n，表示树的节点个数。
接下来n-1行，每行包含两个正整数，u,v，表示u和v在树上有边相连。
【输出格式】
输出n行，第i行表示第i个点为根对应的有根树的最优树链剖分的代价。
【样例输入】
7
4 6
5 4
2 5
1 3
7 4
1 7
【样例输出】
12
6
6
16
12
10
16
【提示】
n<=500000
【来源】
by zys