CF 686D. Kay and Snowflake
2024-09-05 18:24:27
给你一个树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;
}
最新文章
- MFC的本质
- java多线程-Condition
- 泌尿系统 Excretory system
- LeetCode7:Reverse Integer
- Windows+Git+TortoiseGit+COPSSH安装图文教程 转载
- 从 Windows 到 Android: 威胁的持续迁移
- 56个PHP开发常用代码
- (转载)iOS Framework: Introducing MKNetworkKit
- HTML5 canvas入门
- Selenium_chromedriver与chrome版本映射表(更新至v2)
- 打印二叉堆(Java实现)
- Java发送手机短信(附代码和解析,亲测有效,简便易操作)
- POJ 3074 Sudoku(算竞进阶习题)
- 『Numpy』内存分析_利用共享内存创建数组
- git core.autocrlf配置 解决Windows和Linux(Mac)换行问题
- Codeforces 792B. Counting-out Rhyme
- mark1-git
- ios 关于屏幕旋转和屏幕晃动
- 0908期 HTML Frameset框架和选择器
- python 爬虫 黑科技
热门文章
- DP+滚动数组 || [Usaco2007 Nov]Telephone Wire 架设电话线 || BZOJ 1705 || Luogu P2885
- 对所有的webview添加userAgent
- c语言日志打印
- strtok的使用
- CSS中的 vh/vw
- C/C++中结构体引用中箭头->;与点.的区别
- TTTTTTTTTTT LA 4329 BIT模版
- SPOJ 913 Query on a tree II
- (C#- 多线程) 在线程中创建object,共享问题。
- 用smtplib来发送邮件