分析:
还是一个贪心,能合并就合并
因为一个子节点如果不符合条件,那么他一定会和他的根节点合并起来,不然就会不符合条件,也就是说,我们求出以每一个节点为根的子树内部的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; }