给你一颗 贪心 dfs
A. Linova and Kingdom
题意
个节点根为1号节点的树，选
个城市作为工业城市，其余为旅游城市，工业城市的使节每经过旅游城市开心值+1，求所有工业城市的使节到1号节点的开心值的和最大为多少？思路
很容易看出来如果只选一个，一定选距离根节点最远的叶子，我们思考第四个为什么选2而不是3和4，因为选3和4，会减少其子树节点的开心值。（因为我们选这个点，根据贪心我们肯定已经选了所有他子树的节点）
我们求出每个节点的贡献值，排序取最大的k个数即可。#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const double eps = 1e-8; const int NINF = 0xc0c0c0c0; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; const ll maxn = 1e6 + 5; const int N = 2e5 + 5; ll n,k,f[N],s[N]; vector<int>G[N]; void dfs(int x,int fa,ll d){ f[x]=d; s[x]=1; for(int c:G[x]){ if(c==fa) continue; dfs(c,x,d+1); s[x]+=s[c]; f[x]-=s[c]; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; for(int i=1;i<n;i++){ int u,v;cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs(1,-1,0); sort(f+1,f+1+n,greater<ll>()); ll res=0; for(int i=1;i<=k;i++){ res+=f[i]; } cout<<res<<'n'; return 0; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
