2017 ICPC/ACM 沈阳区域赛HDU6228

时间:2022-05-13 04:11:33

Tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 373    Accepted Submission(s): 254

Problem Description
Consider a un-rooted tree T which is not the biological significance of tree or plant, but a tree as an undirected graph in graph theory with n nodes, labelled from 1 to n. If you cannot understand the concept of a tree here, please omit this problem.
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.
 
Input
The first line of input contains an integer T (1 ≤ T ≤ 1000), indicating the total number of test cases.
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.
 
Output
For each test case, output the maximum size of E1 ∩ E1 ... ∩ Ek.
 
Sample Input
3
4 2
1 2
2 3
3 4
4 2
1 2
1 3
1 4
6 3
1 2
2 3
3 4
3 5
6 2
 
Sample Output
1
1

题意 给树节点染色

直接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的更多相关文章

  1. 2017 ICPC&sol;ACM 沈阳区域赛HDU6223

    Infinite Fraction Path Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java ...

  2. 2015年ACM长春区域赛比赛感悟

    距离长春区域赛结束已经4天了,是时候整理一下这次比赛的点点滴滴了. 也是在比赛前一周才得到通知要我参加长春区域赛,当时也是既兴奋又感到有很大的压力,毕竟我的第一场比赛就是区域赛水平,还是很有挑战性的. ...

  3. 2017沈阳区域赛Infinite Fraction Path&lpar;BFS &plus; 剪枝&rpar;

    Infinite Fraction Path Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java ...

  4. 2015沈阳区域赛Meeting&lpar;最短路 &plus; 建图&rpar;

    Meeting Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)Total ...

  5. ICPC 2018 焦作区域赛

    // 2019.10.7 练习赛 // 赛题来源:2018 ICPC 焦作区域赛 // CF链接:http://codeforces.com/gym/102028 A Xu Xiake in Hena ...

  6. 2017 ACM-ICPC 沈阳区域赛记录

    出发日 中午坐大巴前往萧山机场. 哇开心又可以坐飞机了 飞机延误了.在候机大厅里十分无聊,先用机场的电脑玩了会小游戏 然后偷偷切了2个水题 (什么编译器IDE都没有,只能记事本了) 飞机上什么东西都没 ...

  7. hdu6229 Wandering Robots 2017沈阳区域赛M题 思维加map

    题目传送门 题目大意: 给出一张n*n的图,机器人在一秒钟内任一格子上都可以有五种操作,上下左右或者停顿,(不能出边界,不能碰到障碍物).题目给出k个障碍物,但保证没有障碍物的地方是强联通的,问经过无 ...

  8. HDU 6229 Wandering Robots(2017 沈阳区域赛 M题,结论)

    题目链接  HDU 6229 题意 在一个$N * N$的格子矩阵里,有一个机器人. 格子按照行和列标号,左上角的坐标为$(0, 0)$,右下角的坐标为$(N - 1, N - 1)$ 有一个机器人, ...

  9. Infinite Fraction Path HDU 6223 2017沈阳区域赛G题题解

    题意:给你一个字符串s,找到满足条件(s[i]的下一个字符是s[(i*i+1)%n])的最大字典序的长度为n的串. 思路:类似后缀数组,每次倍增来对以i开头的字符串排序,复杂度O(nlogn).代码很 ...

随机推荐

  1. Linux内核装载和启动一个可执行程序

    “平安的祝福 + 原创作品转载请注明出处 + <Linux内核分析>MOOC课程http://mooc.study.163.com/course/USTC-1000029000 ” 理解编 ...

  2. 【转载】理解GL&lowbar;TRIANGLE&lowbar;STRIP等绘制三角形序列的三种方式

    GL_TRIANGLE_STRIP绘制三角形方式很多时候令人疑惑,在这里对其运作机理进行解释. 一般情况下有三种绘制一系列三角形的方式,分别是GL_TRIANGLES.GL_TRIANGLE_STRI ...

  3. P1049送给圣诞夜的礼品&lpar;矩阵十大问题之四)

    https://vijos.org/p/1049 P1049送给圣诞夜的礼品 Accepted 标签:组合数学送给圣诞夜的礼物[显示标签]     返回代码界面 | 关闭   Pascal Pasca ...

  4. collection和collections区别

    collection和collections区别 collection-->是集合类的上级接口,继承他的接口主要有set,list collections-->是针对集合类的一个帮助类,提 ...

  5. BZOJ 2561&colon; 最小生成树&lpar;最小割&rpar;

    U,V能在最小(大)生成树上,当且仅当权值比它小(大)的边无法连通U,V. 两次最小割就OK了. --------------------------------------------------- ...

  6. COC&plus;RTS&plus;MOR游戏开发 一(游戏特色分析,和实践)

    本场比赛的临时名称 游戏特色(-):COC风格 ,塔防养成类游戏.          一款史诗般的战斗策略游戏.玩家须要建立村庄,成千上万的网友训练玩家的军队和战斗. 游戏中玩家须要不断的提高军队的作 ...

  7. 在线资源--图片&sol;json等

    1. 在线图片: http://image.zhangxinxu.com/image/study/s/s256/mm3.jpg  // mmX.jpg: X可为任意的数字 2. 在线json: 雅虎天 ...

  8. springboot情操陶冶-web配置&lpar;五&rpar;

    本文讲讲mvc的异常处理机制,方便查阅以及编写合理的异常响应方式 入口例子 很简单,根据之前的文章,我们只需要复写WebMvcConfigurer接口的异常添加方法即可,如下 1.创建简单的异常处理类 ...

  9. django项目 报错:ImportError&colon; cannot import name choice

    今天项目开发中遇到一个错误,排查了很久才发现原因,现在分享出来,希望对大家有所帮助. 错误描述:在项目中添加了一个random.py的类,导入random中的choice,并在randstr方法中使用 ...

  10. Chrome 浏览器的简单设置 无痕模式 暗黑模式 自定义用户目录

    1. Chrome73 新增加了暗黑模式 可以通过修改快捷方式的方式来默认开启方法如下 1.1 关闭浏览器 2.2 鼠标焦点定位到任务栏 Chrome 图标处, 并且按住shift 按键 执行右键操作 ...