题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3069
题目大意：用最少警力，监控一个树，逮住逃犯。即最大警力去一个子树捉人时，确保父点至少被一个警察看守着。
解题思路：
树结构出点、入点不明确，所以建一个无向树，从任一一个结点开始，肯定能跑完整个树。
对于一个结点，先树形dfs求出所有子树需要布置的最大警力maxSub
捉人策略如下：
边界情况，如果是叶子结点，那么需要一个警力。ans=1
如果相同最大警力子树个数=1，先去把少于最大警力的点捉完，这个结点肯定有警力留守。最后捉这个最大点。ans=maxSub
如果相同最大警力子树个数>=2，说明这个结点需要额外补一个警力，否则去一个最大子树，会被另一个最大子树钻空子。ans=maxSub+1
#include "cstdio"
#include "algorithm"
#include "cstring"
#include "vector"
using namespace std;
#define maxn 1005
int head[maxn],tot,u,v,n;
struct Edge
{
int to,next;
}e[maxn*];
void addedge(int u,int v)
{
e[tot].to=v;
e[tot].next=head[u];
head[u]=tot++;
}
int dfs(int u,int pre)
{
int ans=-,cnt=;
vector<int> check;
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].to,t;
if(v==pre) continue;
t=dfs(v,u);
check.push_back(t);
ans=max(ans,t);
}
if(check.size()==) return ;
for(int i=;i<check.size();i++) if(check[i]==ans) cnt++;
if(cnt>) return ans+;
else return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
int n;
while(scanf("%d",&n)!=EOF)
{
tot=;
memset(head,-,sizeof(head));
for(int i=;i<n-;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
int ans=dfs(,);
printf("%d\n",ans);
}
}