2017ICPC沈阳赛现场赛 L-Tree (dfs)
2024-10-05 15:36:30
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6228
题目大意:给一棵树,需要用k种颜色给树上的节点染色,问你在最优的染色方案下,相同颜色的节点连接的最小边集的交集最大是多少?
解题思路:每一条边要么属于交集中,要么不属于交集中?关键在于如何判定每一条边到底是属于交集的集合还是不属于交集的集合。假设如果某条边左边的点数和右边的点数均大于等于k,那么这条边就一定属于交集中,因为我们可以对左边的点涂k中颜色,对右边的点也涂k种颜色,否则这条边便不属于交集中。那么问题转化为:求每条边左边的节点个数和右边节点的个数,如果两边节点的个数均大于k,则进行计数。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
int n,k;
vector<int> mp[maxn];
int ans;
int dfs(int u,int fa){
int size=mp[u].size();
int sum=;
for(int i=;i<size;i++){
int v=mp[u][i];
if(v==fa)continue;
sum+=dfs(v,u);
}
if(sum>=k&&(n-sum)>=k) ans++;
return sum;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>n>>k;
for(int i=;i<=n;i++)mp[i].clear();
ans=;
int u,v;
for(int i=;i<n;i++){
cin>>u>>v;
mp[u].push_back(v);
mp[v].push_back(u);
}
int lt=dfs(u,v);
int rt=dfs(v,u);
//cout<<lt<<" "<<rt<<endl;
if(lt>=k&&rt>=k) ans--; //u-v边重复计数了一次
cout<<ans<<endl;
}
return ;
}
最新文章
- ABP框架 - 缓存
- Yocto开发笔记之《驱动调试-GPS数据采集》(QQ交流群:519230208)
- swift 2.x学习笔记(一)
- react 评论列表插入评论数据 unshift
- 程序猿每个VPN真卡手
- T-SQL 语句创建Database的SQL mirroring关系
- groot 引入外部模板
- 0816 1459 json &; pickle ,目录导入,目录规范
- 【代码分享】简单html5足球射门游戏分享
- Android Intent 用法全面总结
- C#多线程下载一个文件
- ZOJ 1204 一个集合能组成多少个等式
- iOS 日期时间控件
- Centos下mongodb的安装与配置
- html的文字样式、下行线、删除线、上标、下标等实现方式
- Python开发——解释器安装
- MongoDB 对象操作
- 【原创】QT简单计算器
- Asp.net core使用IIS在windows上进行托管
- WiFi 干扰器,有时间可以去试试呦!