首页 > 代码库 > 【CodeM初赛B轮】A 贪心
【CodeM初赛B轮】A 贪心
【CodeM初赛B轮】A
题目大意：给你一棵树，起初所有点都是白色的，你每次都能选择一个白点i，将这个点i到根路径上的所有到i的距离<k[i]的点都染成黑色（根和i也算，已经被染成黑色的点还是黑色）。问最少需要染多少次才能将所有点都变黑。
n<=100000
题解：显然贪心啊，但是我一开始居然写了树剖。。。
因为叶子节点是一定要染的，所以我们可以将所有点按DFS序排序，从后往前染。记录vis[i]，表示之前已经将所有到i的距离<=vis[i]的点染成了黑色；再维护mx[i]，表示之前染过的点最多能将到i的距离<=mx[i]的点染成黑色。然后用当前的vis和mx去更新fa就行了。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn=100010;int n,cnt,ans;int fa[maxn],tag[maxn],k[maxn],p[maxn],head[maxn],nxt[maxn],to[maxn],ml[maxn];void add(int a,int b){ to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++;}void dfs(int x){ p[++p[0]]=x; for(int i=head[x];i!=-1;i=nxt[i]) dfs(to[i]);}int main(){ scanf("%d",&n); int i,a; memset(head,-1,sizeof(head)); for(i=2;i<=n;i++) scanf("%d",&fa[i]),add(fa[i],i); for(i=1;i<=n;i++) scanf("%d",&k[i]); dfs(1); for(i=n;i>=1;i--) { a=p[i]; ml[a]=max(ml[a],k[a]); if(!tag[a]) tag[a]=ml[a],ans++; ml[fa[a]]=max(ml[fa[a]],ml[a]-1),tag[fa[a]]=max(tag[fa[a]],tag[a]-1); } printf("%d",ans); return 0;}【CodeM初赛B轮】A 贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。