Poj 1655 Balancing Act (DP_树形DP)
题目大意：给定一棵n棵节点的树，删去某个节点后剩下来的分支中肯定会有最大节点数，求所有节点的最大分支节点数的最小值。
解题思路：树形DP.深搜两次，第一次深搜记录从当前节点的子孙节点总数（包括自己）,第一次算预处理，复杂度为O(N),第二次利用第一次的结果找各分支的最大节点数，分支有两种情况，一种是孩子的分支，一种当前节点到父亲节点的那条分支（总数为N-dp[cur])，这样再算N次即可得解。
测试数据：
1
7
2 6
1 2
1 4
4 5
3 7
3 1
代码：
[html]
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 110000
#define max(a,b) (a)>(b)?(a):(b)
struct node {
int v;
node *next;
}*head[MAX],tree[MAX];
int n,m,ptr,dp[MAX],ansval,ansi,cnt;
void Initial() {
cnt = ptr = 0;
ansval = ansi = 2147483647;
memset(dp,0,sizeof(dp));
memset(head,NULL,sizeof(head));
}
void AddEdge(int x,int y) {
tree[ptr].v = y;
tree[ptr].next = head[x],head[x] = &tree[ptr++];
tree[ptr].v = x;
tree[ptr].next = head[y],head[y] = &tree[ptr++];
}
void Dfs_Ini(int s,int pa) {
dp[s] = 1;
node *p = head[s];
while (p != NULL) {
if (p->v != pa) {
Dfs_Ini(p->v,s);
dp[s] += dp[p->v];
}
p = p->next;
}
} www.zzzyk.com
void Dfs_Solve(int son,int pa) {
int i,j,tp,tot = 0;
node *p = head[son];
while (p != NULL) {
if (p->v != pa) {
Dfs_Solve(p->v,son);
tp = dp[p->v];
tot = max(tot,tp);
}
p = p->next;
}
if (tot < n - dp[son])
tot = n - dp[son];
if (tot < ansval)
ansval = tot,ansi = son;
}
int main()
{
int i,j,k,a,b,t;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
Initial();
for (i = 1; i < n; ++i) {
scanf("%d%d",&a,&b);
AddEdge(a,b);
}
Dfs_Ini(1,0); //第一次深搜，记录当前节点的子孙总数
Dfs_Solve(1,0); //更新答案
printf("%d %d\n",ansi,ansval);
}
}
补充：软件开发 , C语言 ,
