每日一题 4.8 黑白树

黑白树

https://ac.nowcoder.com/acm/problem/13249

这是一个用树来提升难度的贪心题(蒟蒻理解
首先当你来到一个新节点时有两种情况
1、此节点能被已染色的子节点覆盖 这时只要更新理论最大覆盖范围
2、此节点不能被已染色的子节点覆盖 选择那个提供最大覆盖范围的子节点染***r>菜鸡的其他理解全在代码里面了QAQ

#include <bits/stdc++.h>
#define ll long long 
ll const maxn=1e5+5;
using namespace std;
struct M{///链式前向星存图
    ll to,next,val;///终点,同起点的上一条边的编号,边权
}edge[maxn<<1];///边集
ll n,x,u,v,cnt,head[maxn],k[maxn],ans;
void add(ll u,ll v)
{
  edge[++cnt].next = head[u];///以u为起点上一条边的编号,也就是与这个边起点相同的上一条边的编号
  edge[cnt].to=v;///终点
  //edge[cnt].val=w;///权值
  head[u]=cnt;///更新以u为起点上一条边的编号
}
int dfs(int u,int fa){
    int sum=0;
    for(int i=head[u];i!=0;i=edge[i].next)
        if(edge[i].to!=fa)///深搜
            sum=max(sum,dfs(edge[i].to,u));///确定染色节点
    if(!sum)///该点未被染色范围覆盖  选子节点中的最大范围染色
    {
        ans++;
        return k[u]-1;///向上移一下减一
    }
    k[fa]=max(k[fa],k[u]-1);///更新子节点能覆盖的最大范围
    return sum-1;
}
int main(){
    scanf("%lld",&n);
    for(int i=2;i<=n;i++)
    {
        scanf("%lld",&x);
        add(x,i);
        add(i,x);
    }
    for(int i=1;i<=n;i++)scanf("%lld",&k[i]);
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}
每日一题题解 文章被收录于专栏

每日一题题解的汇集

全部评论

相关推荐

Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务