帮做ppt网站,如何开发一款app软件,H5响应式网站数据,房管家erp中介管理系统Problem - 1336A - Codeforces
Linova and Kingdom - 洛谷 解析#xff1a; 开始认为分情况讨论 k 小于等于叶子结点和大于叶子结点的情况#xff0c;然后选择深度最深的叶子结点和子孙数量最小的结点#xff0c;但是发现如果把某一个非叶子结点选取#xff0c;那么其子孙…Problem - 1336A - Codeforces
Linova and Kingdom - 洛谷 解析 开始认为分情况讨论 k 小于等于叶子结点和大于叶子结点的情况然后选择深度最深的叶子结点和子孙数量最小的结点但是发现如果把某一个非叶子结点选取那么其子孙的贡献都会减少。 考虑贪心首先DFS出每个节点的深度deep根节点为 0 和每个节点的子孙结点个数 num不带本身这样如果某个结点被选取那么其贡献为 deep - num 所以我们选取最大的 k 个结点累计即可。 此处贪心的正确性证明如果我们要选择某个结点那么他的所有子孙结点肯定要被选择。如果不这样的话那么显然选取他的子孙结点对于答案的贡献更高deep更大num更小所以此时这个结点的子孙结点肯定都被选择所以贡献值为 deep - num
#includebits/stdc.h
using namespace std;
#define int long long
const int N2e55;
int n,k,dis[N];
vectorinte[N];
priority_queueintq;
int dfs(int u,int deep,int fa){dis[u]deep;if(e[u].size()1u!1){ //叶结点 q.push(dis[u]);return 1;}int cnt0;for(int i0;ie[u].size();i){if(e[u][i]!fa) cntdfs(e[u][i],deep1,u);}q.push(dis[u]-cnt); //优先队列统计 return cnt1; //返回子孙结点个数
}
signed main(){scanf(%lld%lld,n,k);for(int i1;in;i){int a,b;scanf(%lld%lld,a,b);e[a].push_back(b);e[b].push_back(a);}dfs(1,0,-1); int res0;while(kq.size()){resq.top();q.pop();k--;}coutres;return 0;
}
