CF685B Kay and Snowflake 贪心

た入场券 2021-11-01 10:16 203阅读 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 条评论，203人围观）

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

相关阅读

相关【反悔贪心】CF1278B CF11B

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

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

相关【贪心】CF1822 E

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

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

相关【贪心】CF1841 D

[Codeforces][] 题意： ![f231a62f84944973acc878c8bcd43a09.png][] ![eed5aa21f67e4bf8a27aad

绝地灬酷狼/ 2024年03月23日 23:24/ 0 赞/ 16 阅读

相关【贪心】CF1779 D

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

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

相关【贪心+构造】CF1806B

[? - Virtual Judge (vjudge.net)][- Virtual Judge _vjudge.net] 题意：给定一个长度为n的数列a，你可以重排这个

素颜马尾好姑娘i/ 2024年03月22日 17:17/ 0 赞/ 17 阅读

相关【贪心】CF1845 C

[Problem - C - Codeforces][] 题意： ![462238034546493bae4dc73170075b68.png][] ![9ad694f7

深藏阁楼爱情的钟/ 2024年03月17日 16:31/ 0 赞/ 12 阅读

相关 B. Mocha and Red and Blue（贪心）

（1）如果第一个位置是问号，分别把当做是R/B，往下模拟（2）如果第一个位置是B，那就直接往下模拟（3）如果第一个位置是R，还是直接往下模拟第二个和第三个只需

曾经终败给现在/ 2022年09月05日 13:57/ 0 赞/ 32 阅读

相关 CF1151B Dima and a Bad XOR

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

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

相关 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 赞/ 161 阅读

相关 CF685B Kay and Snowflake 贪心

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

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