POJ 1655 - Balancing Act 树形DP

来源：恒创科技编辑：恒创科技编辑部

2022-08-12 16:07:58

这题和POJ 3107 - Godfather异曲同工...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<ctime>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 20005
using namespace std;
struct node
{
      int x,y,next;
}line[MAXN*2];
int _next[MAXN],n,AnsData,AnsNote;
bool used[MAXN];
void addline(int x,int y,int m)
{
      line[m].next=_next[x],_next[x]=m;
      line[m].x=x,line[m].y=y;
      return;
}
int dfs(int x)
{
      int k,data=0,num=0,t;
      k=_next[x];
      while (k)
      {
            if (!used[line[k].y])
            {
                  used[line[k].y]=true;
                  t=dfs(line[k].y);
                  data=max(t,data);
                  num+=t;
                  used[line[k].y]=false;
            }
            k=line[k].next;
      }
      num++;
      data=max(data,n-num);
      if ((data<AnsData) || (data==AnsData && AnsNote>x))
         AnsNote=x,AnsData=data;
      return num;
}
int main()
{
      int T,i,num; 
      scanf("%d",&T);
      while (T--)
      {
             scanf("%d",&n);
             memset(_next,0,sizeof(_next));
             num=0;
             for (i=1;i<n;i++)
             {
                   int x,y;
                   scanf("%d%d",&x,&y);
                   addline(x,y,++num);
                   addline(y,x,++num);
             }
             memset(used,false,sizeof(used));
             used[1]=true,AnsData=oo;
             dfs(1);
             printf("%d %d\n",AnsNote,AnsData);
      }
      return 0;
}