CF685B Kay and Snowflake 贪心

た入场券 2021-11-01 10:16 175阅读 0赞

# CF685B Kay and Snowflake #

## 链接 ##

[CF][]

## 题目大意 ##

给你一颗树，询问子树的重心

## 思路 ##

贪心？  
重心肯定是向上走的，所以直接向上跳就好了。  
不优秀的时候就不要跳了 ，因为以后也不能更新了。  
复杂度O（n）（没大仔细想过）

## 代码 ##

#include <bits/stdc++.h> using namespace std; const int N=3e5+7; int read() { int x=0,f=1;char s=getchar(); for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1; for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0'; return x*f; } vector<int> G[N]; int n,m,siz[N],ans[N],fa[N],ma[N]; void dfs_siz(int u) { siz[u]++; for(vector<int>::iterator v=G[u].begin();v!=G[u].end();++v) { dfs_siz(*v); siz[u]+=siz[*v]; ma[u]=max(ma[u],siz[*v]); } } void dfs(int u) { ans[u]=u; for(vector<int>::iterator v=G[u].begin();v!=G[u].end();++v) { dfs(*v); int tmp=ans[*v],now=ma[u]; while(tmp!=u) { if(max(ma[tmp],siz[u]-siz[tmp]) < now) { now=max(ma[tmp],siz[u]-siz[tmp]); ans[u]=tmp; } if(ma[tmp]>siz[u]-siz[tmp]) break; tmp=fa[tmp]; } } } int main() { // freopen("a.in","r",stdin); n=read(),m=read(); for(int i=2;i<=n;++i) { fa[i]=read(); G[fa[i]].push_back(i); } dfs_siz(1); dfs(1); for(int i=1;i<=m;++i) printf("%d\n",ans[read()]); return 0; }

转载于:https://www.cnblogs.com/dsrdsr/p/10783349.html

[CF]: https://codeforces.com/contest/685/problem/B

发表评论取消回复

表情：

评论列表（有 0 条评论，175人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1217B

CF1217B 题意： > 有一个有 $ x $ 个头的龙，你有 $ n $ 种方案，每种方案中包含你可以砍掉的头 $ d\_i $ 和龙会生长的头 $ h...

悠悠/ 2024年04月20日 10:34/ 0 赞/ 7 阅读

相关 CF1214B

CF1214B 解法： > 暴力枚举，时间复杂度 $ O(n) $ CODE: include<iostream> include<cstd...

不念不忘少年蓝@/ 2024年04月20日 10:33/ 0 赞/ 6 阅读

相关 CF1200B

CF1200B 解法： > 贪心。当在第i列时，尽可能多的取走第i列的木块使得袋子里的木块尽可能多 CODE: include<iostre...

本是古典何须时尚/ 2024年04月20日 10:29/ 0 赞/ 4 阅读

相关 CF1197B

CF1197B 题意： > 出n个柱子，每个柱子一个圆盘，其半径各不相同，每次只能将柱子上只有一个圆盘的移到相邻位置，问能否全部移到一个柱子上。解法：...

落日映苍穹つ/ 2024年04月20日 10:28/ 0 赞/ 2 阅读

相关【反悔贪心】CF1278B CF11B

[Problem - 1278B - Codeforces][] 题意： ![c0fbd2f3d4224469b8dd5bb7d049f4ee.png][] 思路： !

以你之姓@/ 2024年03月24日 18:30/ 0 赞/ 14 阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 9 阅读

相关【贪心】CF1779 D

不会1700 [Problem - 1779D - Codeforces][] 题意： ![2812e830d8fc42acaa190aa13f186e7a.png][]

r囧r小猫/ 2024年03月23日 23:20/ 0 赞/ 22 阅读

相关 CF1151B Dima and a Bad XOR

题目乍一看很难做啊！你怎么找出一个xor和大于0的来啊？好像没有固定算法啊！ -------------------- 那就不要用固定算法，用随机算法啊！（欺负那些脑子

素颜马尾好姑娘i/ 2021年12月22日 15:55/ 0 赞/ 140 阅读

相关 CF1083B The Fair Nut and Strings

思路： trie树 + 贪心，参考了[https://www.cnblogs.com/Memory-of-winter/p/10339779.html][https_www.

ゝ一纸荒年。/ 2021年12月10日 17:47/ 0 赞/ 136 阅读

相关 CF685B Kay and Snowflake 贪心

CF685B Kay and Snowflake 链接 [CF][] 题目大意给你一颗树，询问子树的重心思路贪心？重心肯定是向上走的，所

た入场券/ 2021年11月01日 10:16/ 0 赞/ 176 阅读