牛客挑战赛45 B-我是A题

我是 A 题

https://ac.nowcoder.com/acm/contest/8563/B

我是A题

分析:

还是一个贪心,能合并就合并
图片说明
因为一个子节点如果不符合条件,那么他一定会和他的根节点合并起来,不然就会不符合条件,也就是说,我们求出以每一个节点为根的子树内部的w值模k的总和,如果这个子树中的w值为0,说明他可以自成一体,不用再与父节点合并了,反之,则要加上那一条边

代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e6+10;

ll n,k,tot,ans;
ll h[N],nex[N<<1],ver[N<<1],pri[N<<1];
ll w[N];

inline void add(ll x,ll y,ll z)
{
    nex[tot]=h[x];
    ver[tot]=y;
    pri[tot]=z;
    h[x]=tot++;
}

inline void dfs(ll u,ll v)
{
    for (ll i=h[u];~i;i=nex[i])
    {
        ll j=ver[i];
        if(j==v) continue;

        dfs(j,u);

        w[u]=(w[u]+w[j])%k;
        if(w[j]!=0) ans+=pri[i];
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%lld%lld",&n,&k);
    for (ll i=1;i<=n;i++)
        scanf("%lld",&w[i]),w[i]%=k;
    for (ll i=1;i<n;i++)
    {
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }

    dfs(1,0);

    printf("%lld\n",ans);

    return 0;
}
比赛题解 文章被收录于专栏

牛客IOI周赛,团队赛,练习赛,挑战赛,各种模拟赛的部分题解

全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
06-19 19:06
门头沟学院 Java
码农索隆:别去东软,真学不到东西,真事
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
7
收藏
分享

创作者周榜

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