| 题目名称 | 2365. [Codeforces 685B] 树的重心 |
|---|---|
| 输入输出 | kayandsnowflake.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Satoshi
于2016-06-29加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：15， 通过率：80% | ||||
 AAAAAAAAAA |
100 | 0.475 s | 9.35 MiB | C++ |
 TA |
100 | 0.587 s | 21.30 MiB | C++ |
 stdafx.h |
100 | 0.714 s | 11.73 MiB | C++ |
|
stdafx.h |
100 | 0.735 s | 15.55 MiB | C++ |
 神利·代目 |
100 | 0.831 s | 17.46 MiB | C++ |
 Emine |
100 | 0.960 s | 17.48 MiB | C++ |
|
TA |
100 | 1.023 s | 21.30 MiB | C++ |
|
Emine |
100 | 1.103 s | 17.48 MiB | C++ |
|
TA |
100 | 1.159 s | 16.53 MiB | C++ |
 Arrow |
100 | 1.401 s | 13.66 MiB | C++ |
| 本题关联比赛 | |||
| 20190526模拟赛 | |||
| 关于 树的重心 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
 描述有问题 Arrow
2017-09-20 20:11
5楼
| ||||
|
回复 @stdafx.h :
有时间我会加  Satoshi
2016-07-02 22:23
4楼
| ||||
|
没有spj啊.. 一个树可能有好几个重心
stdafx.h
2016-07-02 21:13
3楼
| ||||
|
| ||||
|
题解有三种做法，一种是$O(n \log^2 n+q)$,一种是$O(n +q\log^2 n)$,一种是$O(n+q)$,
| ||||
2365. [Codeforces 685B] 树的重心
★★★ 输入文件：kayandsnowflake.in
输出文件：kayandsnowflake.out
评测插件时间限制：2 s 内存限制：256 MiB
【题目描述】
给定一棵以 $1$ 为根的树，求树的所有子树的重心
一棵树的重心的定义：去掉这个重心后，使得生成的联通分量中节点数最大值最小
【输入格式】
第一行一个整数 $n$
第二行 $n-1$ 个数，第 $i$ 个数表示 $i+1$ 的父亲是 $i$
【输出格式】
总共 $n$ 行，每行一个整数,第 $i$ 行的数表示$i$的子树的重心编号
【样例输入】
7 1 1 3 3 5 3
【样例输出】
3 2 3 4 6 6 7
【数据范围】
对于30%的数据,$n<=1000$
对于60%的数据,$n<=100000$
对于100%的数据,$n<=500000$