http://codeforces.com/contest/686/problem/D

给出q个询问,每次要求询问以x为根的子树中,哪一个点是重心。

树的重心:求以cur为根的子树的重心,就是要找一个点,使得删除这个点后,分开来的零散的子树中,节点数的最大值最小。并且最大值最多也只是son[cur] / 2,因为最坏情况(最难分)也就是一条直线,选中间点就可以了。

例如

询问1的时候,就应该删除3,然后得到4个零散分支,2个大小是1,2个是2。

算法思路:

直观来说,应该是删除那个儿子数最多的那个节点的。 比如上图,3的儿子数最多,所以询问1就删除3了。因为,没理由再分一些节点给最大的那颗子树把,这样只会更坏。

但是却可以把最大的那颗子树分一些节点去另一边,所以优先删除最大的那颗子树的重心,然后判断是否符合要求,不符合就只能暴力往上找了。

判定条件是son[cur] > 2 * son[重心]就不行。

因为这表明son[cur] - son[重心]的值还大于son[cur] / 2

代进去就知道了son[cur] - son[重心] > son[重心],

假设son[cur] = 2 * son[重心]。那么就是剩下的节点数会大于son[cur] / 2咯。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int ans[maxn];
int son[maxn]; //第u个点有多少个儿子。
int fa[maxn]; //记录第i个点的爸爸是谁
struct node {
int u, v, tonext;
}e[maxn];
int first[maxn]; int num;
void add(int u, int v) {
++num;
e[num].u = u;
e[num].v = v;
e[num].tonext = first[u];
first[u] = num;
}
void dfs(int cur, int from) {
son[cur] = ; //自己一个
ans[cur] = cur; //叶子节点
int mx = -inf, pos = cur; //以这个点为子树的儿子数最多的那个pos
for (int i = first[cur]; i; i = e[i].tonext) {
dfs(e[i].v, cur);
son[cur] += son[e[i].v]; //加上儿子的节点个数
if (mx < son[e[i].v]) { //不能算自己,只能算儿子的max
mx = son[e[i].v];
pos = e[i].v; //儿子数最多的那个节点,
}
}
ans[cur] = ans[pos]; //ans[pos]已经算出来了,ans[pos]的重心
while (son[cur] > * son[ans[cur]]) {
ans[cur] = fa[ans[cur]]; //暴力往上找
}
}
void work() {
int n;
cin >> n;
int q;
cin >> q;
for (int i = ; i <= n; ++i) {
int x;
cin >> x;
add(x, i);
fa[i] = x;
}
dfs(, -);
for (int i = ; i <= q; ++i) {
int x;
cin >> x;
cout << ans[x] << endl;
}
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
IOS;
work();
return ;
}

重心的定义是:

找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后,生成的多棵树尽可能平衡

(一)
树中所有点到某个点的距离和中,到重心的距离和是最小的;如果有两个重心,那么他们的距离和一样。

(二)
把两个树通过一条边相连得到一个新的树,那么新的树的重心在连接原来两个树的重心的路径上。

(三)

把一个树添加或删除一个叶子,那么它的重心最多只移动一条边的距离。

最新文章

  1. Web性能测试工具JMeter
  2. Spring MVC异常处理详解
  3. Ranorex入门指南
  4. PL/SQL — 隐式游标
  5. python GUI学习——Tkinter
  6. $.ajax和vue-resource实现OAuth
  7. Swift - 多行文本输入框(UITextView)的用法
  8. 学习javascript 的一点感想
  9. 转 Android:sp与dp(densityDpi与scaledDensity)
  10. CLR类型设计之泛型(一)
  11. SpringCloud是否值得引入?
  12. A-the Beatles
  13. Android实现对HOME键的捕获和屏蔽
  14. 如何将shell的打印日志输入到日志文件
  15. Google ProtocolBuffers2.4.1应用说明(一)
  16. 【云迁移论文笔记】Cloud Migration Research:A Systematic Review
  17. 基于jQuery的Cookie操作插件--简单而又没有兼容性问题!
  18. zoj3822
  19. PHP实现登录功能DEMO
  20. Tomcat设置开启时自动访问某个servlet类存在的问题

热门文章

  1. awk 根据外部变量匹配某一域值
  2. laravel基础课程---2、Laravel配置文件、路由及php artisan(php artisan是什么)
  3. mongodb给我们提供了fsync+lock机制把数据暴力的刷到硬盘上
  4. Opencv— — Twirl Filter
  5. java.io.FileNotFoundException:/mnt/sdcard/......(Permission denied)
  6. Preface Numbering
  7. C++之STL迭代器
  8. 利用openssl进行base64的编码与解码
  9. virtualBox中的centOS虚拟机硬盘扩容
  10. jsoup解析xml某片段的问题