poj1655 Balancing Act 【树形DP（很弱）】

本文主要是介绍poj1655 Balancing Act 【树形DP（很弱）】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

都不知道怎么分类了。

大概要求一个树中以某个结点为根的子树结点个数，还有儿子结点中以儿子结点为根的子树结点个数的最大值，用递归得到n[i]，以i为根节点的子树结点个数

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
#define scan(a) scanf("%d",&(a))
#define M(a) memset((a),0,sizeof((a)))
vector<int> g[22222];
int n[22222];
int n_max[22222];
int T;
int num;
void input()
{M(n);M(n_max);for(int i=0;i<22222;i++)g[i].clear();scan(num);int tmp1,tmp2;for(int i=0;i<num-1;i++){scan(tmp1);scan(tmp2);g[tmp1].push_back(tmp2);g[tmp2].push_back(tmp1);}
}
int dfs(int i,int fa)
{if(g[i].size()==1&&fa!=-1){return n[i]=1;}int ans=1;int tmpmax=0;for(int j=0;j<g[i].size();j++){if(g[i][j]!=fa){int nn=dfs(g[i][j],i);tmpmax=max(tmpmax,nn);ans+=nn;}}n_max[i]=tmpmax;return n[i]=ans;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("G:/1.txt","r",stdin);freopen("G:/2.txt","w",stdout);#endifscan(T);while(T--){input();dfs(1,-1);int minn=(1<<30);int mindex;for(int i=1;i<=num;i++){int num_minus_ni=num-n[i];int maxin_i=max(num_minus_ni,n_max[i]);if(minn>maxin_i){minn=maxin_i;mindex=i;}}cout<<mindex<<" "<<minn<<'\n';}
}

 

这篇关于poj1655 Balancing Act 【树形DP（很弱）】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---