原题地址：https://ac.nowcoder.com/acm/contest/8563/B
贪心的思路相当明显：对于只有一条边的点，可以单独划分就单独划分，不能就跟找其他点一起。
重点在于，怎么证明贪心是最优的，但是卡在这里。
现在想到以1为根，把图转化为了有层次关系的树。
然后dfs到叶子节点，然后开始操作，能单独划分就单独划分，不能并其他的点。
这样就不会出现该单独划分的点，被其他不能单独划分的点先并走了。
#include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<vector> #include<set> #include<iomanip> #define inf 0x3f3f3f3f #define ll long long using namespace std; const int N=1e6+7; int n,k; ll a[N],u,v,w,ans=0; ll tot=0,to[N<<1],head[N<<1],nxt[N<<1],cost[N<<1]; void add(ll u,ll v,ll w){ nxt[++tot]=head[u]; to[tot]=v; cost[tot]=w; head[u]=tot; } void dfs(int u,int fa){ for(ll i=head[u];i;i=nxt[i]){ ll v=to[i]; if(v==fa) continue; dfs(v,u); a[u]=(a[u]+a[v])%k;//当前节点加上下探节点后的节点值。 //如果下探节点为k倍，无影响 //如果下探节点不为k倍，加上下探节点的值 if(a[v]!=0) ans+=cost[i]; } } int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;++i){ scanf("%lld",&a[i]); a[i]%=k; } for(int i=1;i<n;++i){ scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w);add(v,u,w); } dfs(1,0); printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/PdrEam/p/13975356.html