算法：poj 1655 Balancing Act（树形dp）

题意

一n个节点的棵树，去掉某个节点后，会变成一个森林.

这个森林中的每个树都有个节点数量， 其中最大节点数设为max

问删除某个节点后，max最小可以多少？

思路

和poj-3107 GodFather完全一样！ 不想吐槽了。。。

其实本来不想发这篇，不过发现今天是八月最后一天，而且 还差一篇就发了80篇了。。于是。。就很邪恶的水了

代码

/**=====================================================
* This is a solution for ACM/ICPC problem
*
* @source : poj-1655 Balancing Act
* @description : 树形dp
* @author : shuangde
* @blog : blog.csdn.net/shuangde800
* @email : zengshuangde@gmail.com
* Copyright (C) 2013/08/31 15:32 All rights reserved.
*======================================================*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

typedef pair<int, int >PII;
typedef long long int64;
const int INF = 0x3f3f3f3f;

const int MAXN = 20010;
int tot[MAXN];
int f[MAXN], minx, id;

namespace Adj {
int size, head[MAXN];
struct Node{
int v, next;
}E[MAXN*2];
inline void initAdj() {
size = 0;
memset(head, -1, sizeof(head));
}
inline void addEdge(int u, int v) {
E[size].v = v;
E[size].next = head[u];
head[u] = size++;
}
}
using namespace Adj;

int n;

int dfs(int u, int fa) {

tot[u] = 1;
// count
// http://www.bianceng.cn
for (int e = head[u]; e != -1; e = E[e].next) {
int v = E[e].v;
if (v == fa) continue;
tot[u] += dfs(v, u);
}
// 保存答案
int& ans = f[u] = n - tot[u];
for (int e = head[u]; e != -1; e = E[e].next) {
int v = E[e].v;
if (v == fa) continue;
ans = max(ans, tot[v]);
}
if (ans < minx) {
minx = ans;
id = u;
} else if(ans == minx) {
id = min(id, u);
}
return tot[u];
}

int main(){
int nCase;
scanf("%d", &nCase);

while (nCase--) {
scanf("%d", &n);

initAdj();
for (int i = 0; i < n - 1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
minx = INF;
dfs(1, -1);
printf("%d %d\n", id, minx);
}

return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， namespace
， include
， 节点
， head
， an d
size
balancing act、a balancing act、树形dp、树形dp入门、bzoj 树形dp，以便于您获取更多的相关知识。