Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 373 Accepted Submission(s): 254
Now we decide to colour its nodes with k distinct colours, labelled from 1 to k. Then for each colour i = 1, 2, · · · , k, define Ei as the minimum subset of edges connecting all nodes coloured by i. If there is no node of the tree coloured by a specified colour i, Ei will be empty.
Try to decide a colour scheme to maximize the size of E1 ∩ E2 · · · ∩ Ek, and output its size.
For each case, the first line contains two positive integers n which is the size of the tree and k (k ≤ 500) which is the number of colours. Each of the following n - 1 lines contains two integers x and y describing an edge between them. We are sure that the given graph is a tree.
The summation of n in input is smaller than or equal to 200000.
题意 给树节点染色
直接dfs搜一遍就好了
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <ctime>
#include <vector>
using namespace std;
const int maxn= 1e5+;
const int maxm= 1e6+;
const int inf = 0x3f3f3f3f;
typedef long long ll;
vector<int> G[maxn];
int n,k,ans;
int siz[maxn];
void dfs(int x,int fa)
{
siz[x]=;
for(int i=;i<G[x].size();i++)
{
int w=G[x][i];
if(w!=fa)
{
dfs(w,x);
siz[x]+=siz[w];
}
}
if(siz[x]>=k&&n-siz[x]>=k)
ans++;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
int u,v;
for(int i=;i<=n;i++)
G[i].clear();
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
ans=;
dfs(,);
printf("%d\n",ans);
}
}
2017 ICPC/ACM 沈阳区域赛HDU6228的更多相关文章
-
2017 ICPC/ACM 沈阳区域赛HDU6223
Infinite Fraction Path Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java ...
-
2015年ACM长春区域赛比赛感悟
距离长春区域赛结束已经4天了,是时候整理一下这次比赛的点点滴滴了. 也是在比赛前一周才得到通知要我参加长春区域赛,当时也是既兴奋又感到有很大的压力,毕竟我的第一场比赛就是区域赛水平,还是很有挑战性的. ...
-
2017沈阳区域赛Infinite Fraction Path(BFS + 剪枝)
Infinite Fraction Path Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java ...
-
2015沈阳区域赛Meeting(最短路 + 建图)
Meeting Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total ...
-
ICPC 2018 焦作区域赛
// 2019.10.7 练习赛 // 赛题来源:2018 ICPC 焦作区域赛 // CF链接:http://codeforces.com/gym/102028 A Xu Xiake in Hena ...
-
2017 ACM-ICPC 沈阳区域赛记录
出发日 中午坐大巴前往萧山机场. 哇开心又可以坐飞机了 飞机延误了.在候机大厅里十分无聊,先用机场的电脑玩了会小游戏 然后偷偷切了2个水题 (什么编译器IDE都没有,只能记事本了) 飞机上什么东西都没 ...
-
hdu6229 Wandering Robots 2017沈阳区域赛M题 思维加map
题目传送门 题目大意: 给出一张n*n的图,机器人在一秒钟内任一格子上都可以有五种操作,上下左右或者停顿,(不能出边界,不能碰到障碍物).题目给出k个障碍物,但保证没有障碍物的地方是强联通的,问经过无 ...
-
HDU 6229 Wandering Robots(2017 沈阳区域赛 M题,结论)
题目链接 HDU 6229 题意 在一个$N * N$的格子矩阵里,有一个机器人. 格子按照行和列标号,左上角的坐标为$(0, 0)$,右下角的坐标为$(N - 1, N - 1)$ 有一个机器人, ...
-
Infinite Fraction Path HDU 6223 2017沈阳区域赛G题题解
题意:给你一个字符串s,找到满足条件(s[i]的下一个字符是s[(i*i+1)%n])的最大字典序的长度为n的串. 思路:类似后缀数组,每次倍增来对以i开头的字符串排序,复杂度O(nlogn).代码很 ...
随机推荐
-
Linux内核装载和启动一个可执行程序
“平安的祝福 + 原创作品转载请注明出处 + <Linux内核分析>MOOC课程http://mooc.study.163.com/course/USTC-1000029000 ” 理解编 ...
-
【转载】理解GL_TRIANGLE_STRIP等绘制三角形序列的三种方式
GL_TRIANGLE_STRIP绘制三角形方式很多时候令人疑惑,在这里对其运作机理进行解释. 一般情况下有三种绘制一系列三角形的方式,分别是GL_TRIANGLES.GL_TRIANGLE_STRI ...
-
P1049送给圣诞夜的礼品(矩阵十大问题之四)
https://vijos.org/p/1049 P1049送给圣诞夜的礼品 Accepted 标签:组合数学送给圣诞夜的礼物[显示标签] 返回代码界面 | 关闭 Pascal Pasca ...
-
collection和collections区别
collection和collections区别 collection-->是集合类的上级接口,继承他的接口主要有set,list collections-->是针对集合类的一个帮助类,提 ...
-
BZOJ 2561: 最小生成树(最小割)
U,V能在最小(大)生成树上,当且仅当权值比它小(大)的边无法连通U,V. 两次最小割就OK了. --------------------------------------------------- ...
-
COC+RTS+MOR游戏开发 一(游戏特色分析,和实践)
本场比赛的临时名称 游戏特色(-):COC风格 ,塔防养成类游戏. 一款史诗般的战斗策略游戏.玩家须要建立村庄,成千上万的网友训练玩家的军队和战斗. 游戏中玩家须要不断的提高军队的作 ...
-
在线资源--图片/json等
1. 在线图片: http://image.zhangxinxu.com/image/study/s/s256/mm3.jpg // mmX.jpg: X可为任意的数字 2. 在线json: 雅虎天 ...
-
springboot情操陶冶-web配置(五)
本文讲讲mvc的异常处理机制,方便查阅以及编写合理的异常响应方式 入口例子 很简单,根据之前的文章,我们只需要复写WebMvcConfigurer接口的异常添加方法即可,如下 1.创建简单的异常处理类 ...
-
django项目 报错:ImportError: cannot import name choice
今天项目开发中遇到一个错误,排查了很久才发现原因,现在分享出来,希望对大家有所帮助. 错误描述:在项目中添加了一个random.py的类,导入random中的choice,并在randstr方法中使用 ...
-
Chrome 浏览器的简单设置 无痕模式 暗黑模式 自定义用户目录
1. Chrome73 新增加了暗黑模式 可以通过修改快捷方式的方式来默认开启方法如下 1.1 关闭浏览器 2.2 鼠标焦点定位到任务栏 Chrome 图标处, 并且按住shift 按键 执行右键操作 ...