题意:一个对于一个树,除了一号点之外,其余点分成K个集合,接下来每个集合分别和一号点并在一起组成新的集合,求每个集合里边点形成的最小生成树的值,(借助集合外边的点)。然后问这k个最小生成树的最大总和是多少。
思路:明显对于同一集合的点尽量不分在同一子树中边权和才更大,把1看成整棵树的根. 可知道如果一号点作为根,每一个集合的点都是要连接一号点的,反向思维,答案即为边对此边连着的子树里面的点的种类个数即为min(siz[u],k),贡献即为cost*min(siz[u],k)dfs求和即可;子节点和父节点不在同一个集合中。
代码如下:
#include<iostream> #include<cstdio> #include<vector> using namespace std; const int MAXN=1e6+10; typedef long long ll; ll Cost[MAXN],sz[MAXN]; struct node { int v,cost; node(int _v=0,int _cost=0):v(_v),cost(_cost){} }; vector<node>E[MAXN]; ll ans; void dfs(int root,int fa) { sz[root]=1; int size=E[root].size(); for(int i=0;i<size;i++) { int v=E[root][i].v,c=E[root][i].cost; Cost[v]=c; if(v==fa)continue; dfs(v,root); sz[root]+=sz[v]; } } int main() { //freopen("C:\Users\Administrator\Desktop\a.txt","r",stdin); int n,k; while(scanf("%d%d",&n,&k)!=EOF) { int u,v,c; for(int i=0;i<=n;i++)E[i].clear(),sz[i]=0,Cost[i]=0; for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&c); E[u].push_back(node(v,c)); } ans=0; dfs(1,-1); for(int i=1;i<=n;i++) ans+=Cost[i]*(min(sz[i],(ll)k));//,printf("i %d sz %d c %d ",i,sz[i],Cost[i]); printf("%lld ",ans); //printf("%lld ",ans); } return 0; }