CF685B Kay and Snowflake 贪心

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

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

相关阅读

相关【反悔贪心】CF1278B CF11B

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

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

相关【贪心】CF1822 E

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

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

相关【贪心+构造】CF1806B

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

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

相关【Tree树上染色+贪心】CF1387B1

[Problem - 1387B1 - Codeforces][] 题意： ![946309f0da624ae09c2715a343db0b1d.png][] ![0a3

柔光的暖阳◎/ 2024年03月16日 07:40/ 0 赞/ 50 阅读

相关贪心——cf708b

先求0，1的个数，然后贪心输出01即可 include<bits/stdc++.h> using namespace std; define ll l

朴灿烈づ我的快乐病毒、/ 2023年10月12日 08:21/ 0 赞/ 38 阅读

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

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

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

相关 CF 460B Little Dima and Equation

题目链接：http://codeforces.com/problemset/problem/460/B 题意：输入a，b，c 0 < x < 109 x = b

快来打我*/ 2022年08月09日 15:51/ 0 赞/ 14 阅读

相关 CF1151B Dima and a Bad XOR

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

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

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

相关 CF685B Kay and Snowflake 贪心

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

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