【ISA的胡策】训练8.25（博弈）

题目：


题解：
这道题算是最简单的博弈问题，结论题？答案就是最大的叶子结点
先手要求最大，后手要求最小，如果先手直接砍最大的叶子结点a,可以得到的
x>=a，如果先手砍别的点，后手会砍x<=a，后手可能砍到更小的点，不如先手直接砍掉最大叶子结点呢
代码：

#include <cstdio>
#include <iostream>
#define N 1050
using namespace std;
int nxt[N],point[N],v[N],tot,a[N],maxx;
void addline(int x,int y)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
void dfs(int x,int fa)
{
    bool fff=false;
    for (int i=point[x];i;i=nxt[i])
      if (v[i]!=fa)
      {
        fff=true;
        dfs(v[i],x);
      }
    if (!fff) maxx=max(maxx,a[x]);
}
int main()
{
    int n,i;
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addline(x,y);
    }
    for (i=1;i<=n;i++) dfs(i,0);
    printf("%d",maxx);
}