博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 1655 Balancing Act[树的重心/树形dp]
阅读量:5879 次
发布时间:2019-06-19

本文共 2715 字,大约阅读时间需要 9 分钟。

时限:1000ms

Description

Consider a tree T with N (1 <= N <= 20,000) nodes numbered 1...N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T
created by deleting that node from T. 
For example, consider the tree: 
Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two. 
For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number. 

Input

The first line of input contains a single integer t (1 <= t <= 20), the number of test cases. The first line of each test case contains an integer N (1 <= N <= 20,000), the number of congruence. The next N-1 lines each contains two space-separated node numbers that are the endpoints of an edge in the tree. No edge will be listed twice, and all edges will be listed.

Output

For each test case, print a line containing two integers, the number of the node with minimum balance and the balance of that node.

Sample Input

172 61 21 44 53 73 1

Sample Output

1 2 树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后,生成的多棵树尽可能平衡。 利用树形dp的思想,对节点u的子树进行遍历。和树的直径不同的是,如果子树的分割确定了,那么子树之外的节点必定在一颗树上,不需要在dfs一次。
#include "stdio.h"#include "algorithm"#include "string.h"using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 20000 + 10;bool vis[maxn];struct edge {    int to, next;} e[maxn*2];int n, num[maxn];int size, cur;int tot = 0;int head[maxn];void add_edge(int u, int v) {    e[tot].to = v; e[tot].next = head[u];    head[u] = tot++;}void dfs(int u) {    num[u] = 0;    int tr = 0;    vis[u] = true;    for (int i = head[u]; i != -1; i = e[i].next) {        int v = e[i].to;        if (vis[v]) continue;        dfs(v);        num[u] += num[v] + 1;        tr = max(num[v] + 1, tr);    }     tr = max(n - num[u] - 1, tr); //剩下那棵树的大小    if (tr < size || tr == size && cur > u) { //答案还要编号节点最小        size = tr; cur = u;    }}void init() {    memset(vis, false, sizeof(vis));    memset(head, -1, sizeof(head));    tot = 0; size = INF;}int main(int argc, char const *argv[]){    int T;    scanf("%d", &T);    while (T--) {        init();        scanf("%d", &n);        for (int i = 0; i < n-1; i++) {            int u, v;            scanf("%d%d", &u, &v); add_edge(u, v);            add_edge(v, u);        }        dfs(1);        printf("%d %d\n", cur, size);    }    return 0;}

 

 

转载于:https://www.cnblogs.com/cniwoq/p/7247542.html

你可能感兴趣的文章
android camera(四):camera 驱动 GT2005
查看>>
一起谈.NET技术,ASP.NET伪静态的实现及伪静态的意义
查看>>
20款绝佳的HTML5应用程序示例
查看>>
string::c_str()、string::c_data()及string与char *的正确转换
查看>>
11G数据的hive初测试
查看>>
如何使用Core Text计算一段文本绘制在屏幕上之后的高度
查看>>
==和equals区别
查看>>
2010技术应用计划
查看>>
XML 节点类型
查看>>
驯服 Tiger: 并发集合 超越 Map、Collection、List 和 Set
查看>>
Winform开发框架之权限管理系统改进的经验总结(3)-系统登录黑白名单的实现...
查看>>
Template Method Design Pattern in Java
查看>>
MVC输出字符串常用四个方式
查看>>
LeetCode – LRU Cache (Java)
查看>>
JavaScript高级程序设计--对象,数组(栈方法,队列方法,重排序方法,迭代方法)...
查看>>
【转】 学习ios(必看经典)牛人40天精通iOS开发的学习方法【2015.12.2
查看>>
nginx+php的使用
查看>>
在 ASP.NET MVC 中使用异步控制器
查看>>
SQL语句的执行过程
查看>>
Silverlight开发历程—动画(线性动画)
查看>>