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

我是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;
}