给你一个树N个点,再给出Q个询问,问以x为根的子树中,重心是哪个?
2≤n≤300000,1≤q≤30000

Sol:
从下到上,根据性质做一下.
1:如果某个点x,其子树y的大小超过总结点个数一半,则重心在y这个子树中。
2:如果某个树的重心点,其上方点的个数多于其下方点的,则重心要上移

#include <bits/stdc++.h>
using namespace std;
const int N = 300000+10;
int n,q;
vector<int> G[N]; ///存图
int ans[N]; ///答案
int son[N]; ///包括自身在内有多少子树结点
int fa[N]; ///输入用,同时代表这个点的父亲 void dfs(int u){
ans[u] = u;//当只有一个点时,重心为其自己
son[u] = 1;
for(int i = 0;i < G[u].size();i++){
int v = G[u][i];
dfs(v);
son[u] += son[v];
}
for(int i = 0;i < G[u].size();i++)
if(son[G[u][i]]*2 > son[u])
//如果有一个子树超过总个数一半,则重心在这个子树中
ans[u] = ans[G[u][i]];
while((son[u]-son[ans[u]])*2 > son[u])
//如果当前重心上方的点,比它下方的点要多,则重心要进行移动
ans[u] = fa[ans[u]];
} int main(void)
{
scanf("%d%d",&n,&q);
for(int i = 2;i <= n;i++){
scanf("%d",&fa[i]);
G[fa[i]].push_back(i);
}
dfs(1);
for(int i = 1;i <= q;i++){
int qq;
scanf("%d",&qq);
printf("%d\n",ans[qq]);
}
return 0;
}

  

最新文章

  1. MFC的本质
  2. java多线程-Condition
  3. 泌尿系统 Excretory system
  4. LeetCode7:Reverse Integer
  5. Windows+Git+TortoiseGit+COPSSH安装图文教程 转载
  6. 从 Windows 到 Android: 威胁的持续迁移
  7. 56个PHP开发常用代码
  8. (转载)iOS Framework: Introducing MKNetworkKit
  9. HTML5 canvas入门
  10. Selenium_chromedriver与chrome版本映射表(更新至v2)
  11. 打印二叉堆(Java实现)
  12. Java发送手机短信(附代码和解析,亲测有效,简便易操作)
  13. POJ 3074 Sudoku(算竞进阶习题)
  14. 『Numpy』内存分析_利用共享内存创建数组
  15. git core.autocrlf配置 解决Windows和Linux(Mac)换行问题
  16. Codeforces 792B. Counting-out Rhyme
  17. mark1-git
  18. ios 关于屏幕旋转和屏幕晃动
  19. 0908期 HTML Frameset框架和选择器
  20. python 爬虫 黑科技

热门文章

  1. DP+滚动数组 || [Usaco2007 Nov]Telephone Wire 架设电话线 || BZOJ 1705 || Luogu P2885
  2. 对所有的webview添加userAgent
  3. c语言日志打印
  4. strtok的使用
  5. CSS中的 vh/vw
  6. C/C++中结构体引用中箭头-&gt;与点.的区别
  7. TTTTTTTTTTT LA 4329 BIT模版
  8. SPOJ 913 Query on a tree II
  9. (C#- 多线程) 在线程中创建object,共享问题。
  10. 用smtplib来发送邮件