来自"NOCOW"

首先这道题要看清题目,题目给出的是个树，而且两个恐怖分子是一起行动的，马上想到树型Dp。

首先把他给的无根树，变成以K为根的树，设f[i]=true表示走到这个节点时第一个走的会赢，=false表示第二个走的会赢，depth[i]表示i在这颗树中的深度，那么方程就出来了

1)depth[i] is odd

f[i]=false; //初值

f[i]=f[i] or f[son[i]]; //转移

2)depth[i] is even

f[i]=true;//初值

f[i]=f[i] and f[son[i]];//转移

program cao;
const
  maxn=1000;
 
var
  map:array[0..maxn,0..maxn] of  boolean;
  t:array[0..maxn,0..maxn] of longint;
  d:array[0..maxn] of longint;
  f,flag:array[0..maxn] of boolean;
  a,b,c,e,g,h,i,j,k,l,n,m,p,q:longint;
 
procedure workout_tree(v:longint);
var
  i:longint;
begin
  flag[v]:=true;
  for i:=1 to n do
    if (flag[i]=false)and(map[v,i]) then
    begin
      inc(d[v]);
      t[v,d[v]]:=i;
      workout_tree(i);
    end;
end;
 
procedure init;
begin
  read(n,k);
  for i:=1 to n-1 do
  begin
    read(a,b);
    map[a,b]:=true;
    map[b,a]:=true;
  end;
  workout_tree(k);
end;
 
procedure search(depth,v:longint);
var
  i:longint;
begin
  if d[v]=0 then
  begin
    f[v]:=odd(depth)=false;
    exit;
  end;
  for i:=1 to d[v] do
    search(depth+1,t[v,i]);
  if odd(depth) then
  begin
    f[v]:=false;
    for i:=1 to d[v] do
      f[v]:=f[v] or f[t[v,i]];
  end
  else
  begin
    f[v]:=true;
    for i:=1 to d[v] do
      f[v]:=f[v] and f[t[v,i]];
  end;
end;
 
procedure main;
begin
  search(1,k);
end;
 
procedure print;
begin
  if f[k]=false then
    writeln(‘First player loses’)
  else
  begin
    for i:=1 to d[k] do
      if f[t[k,i]] then break;
    writeln(‘First player wins flying to airport ‘,t[k,i]);
  end;
end;
 
begin
  init;
  main;
  print;
end.

var
  i,j,k,l,m,n,ans:longint;
  win:array[1..1000]of boolean;
  a:array[1..1000,0..1000]of longint;
 
procedure dp(f,i:longint);
var j,k:longint;
begin
  if a[i,0]=1 then begin win[i]:=false; exit; end;
  win[i]:=false;
  for j:=1 to a[i,0] do
    if a[i,j]<>f then
    begin
      k:=a[i,j];
      dp(i,k);
      if not win[k] then win[i]:=true;
    end;
end;
 
begin
  assign(input,'1045.in');reset(input);
  fillchar(a,sizeof(a),0);
  read(n,m);
  for k:=1 to n-1 do
    begin
      read(i,j);
      inc(a[i,0]); a[i,a[i,0]]:=j;
      inc(a[j,0]); a[j,a[j,0]]:=i;
    end;
  ans:=2000;
  for j:=1 to a[m,0] do
    begin
      dp(m,a[m,j]);
      if not win[a[m,j]] then
        if a[m,j]<ans then ans:=a[m,j];
    end;
  if ans=2000 then writeln('First player loses')
              else writeln('First player wins flying to airport ',ans);
  close(input);
end.

---

const maxn=1000;
 
type node=^nd;
     nd=record nam:longint; next:node; end;
 
var i,j,k,m,n,l:longint;
    a:array[1..maxn]of node;
    son,fa:array[1..maxn]of longint;
    v,f:array[1..maxn]of boolean;
    p:node;
    ans:longint;
 
procedure add(j,k:longint);
begin new(p); p^.nam:=k; p^.next:=a[j]; a[j]:=p; end;
 
procedure dfs(i:longint);
var p:node;
begin
     p:=a[i];
     while p<>nil do
     begin
          if fa[i]<>p^.nam then
          begin fa[p^.nam]:=i; inc(son[i]); dfs(p^.nam); end;
          p:=p^.next;
     end;
end;
 
begin
     readln(n,m);
     for i:=1 to n-1 do
     begin readln(j,k); add(j,k); add(k,j); end;
     dfs(m);
     for i:=1 to n-1 do
     begin
          for j:=1 to n do if not v[j] then
            if son[j]=0 then
            begin
                 f[j]:=true;
                 dec(son[fa[j]]);
                 v[j]:=true;
                 p:=a[j];
                 while p<>nil do
                 begin
                      if v[p^.nam] and f[p^.nam] then
                      begin f[j]:=false; break; end;
                      p:=p^.next;
                 end;
                 break;
            end;
     end;
     p:=a[m];
     ans:=maxlongint;
     while p<>nil do
     begin
          if f[p^.nam] and (p^.nam<ans) then ans:=p^.nam;
          p:=p^.next;
     end;
     if ans=maxlongint then writeln('First player loses')
     else writeln('First player wins flying to airport ',ans);
end.