Atcoder 杂题
AGC014D
大意：两人轮流给树黑白染色（白先手），若最终存在一个白点周围都是白点，白胜，问胜负
题解：
- 当一个点与两个或以上叶子相邻时白必胜
- 若它只与一个叶子相邻，将它和这个叶子删掉（一个叶子白点相当于边界的作用）
1 #include<bits/stdc++.h>
2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
4 #define mem(i,j) memset(i,j,sizeof(i))
5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
6 #define fi first
7 #define se second
8 #define pii pair<int,int>
9 #define MP make_pair
10 using namespace std;
11 typedef long long ll;
12 const int N=1e5+5;
13 int n,a,b,lf[N],d[N],rt;
14 int tot=0,f[N],nxt[N<<1];
15 struct E
16 {
17 int u,v;
18 }e[N<<1];
19 inline void add(int u,int v)
20 {
21 tot++;
22 nxt[tot]=f[u];
23 f[u]=tot;
24 e[tot]=(E){u,v};
25 return;
26 }
27 inline int read()
28 {
29 int x=0,f=1;
30 char c=getchar();
31 while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
32 while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
33 return f*x;
34 }
35 inline void write(int x)
36 {
37 if (x<0) putchar('-'),x=-x;
38 if (x>9) write(x/10);
39 putchar(x%10+'0');
40 return;
41 }
42 inline void yes() {printf("First\n");exit(0);}
43 inline void no() {printf("Second\n");exit(0);}
44 inline int dfs(int u,int fa)
45 {
46 int cnt=0;
47 GO(u)
48 {
49 int v=e[j].v;
50 if (v==fa) continue;
51 cnt+=dfs(v,u);
52 }
53 if (cnt>1) yes();
54 return cnt^1;
55 }
56 int main()
57 {
58 mem(f,-1);
59 n=read();
60 if (n==2) no();
61 if (n==1) yes();
62 FOR(i,1,n-1) a=read(),b=read(),add(a,b),add(b,a),d[a]++,d[b]++;
63 FOR(i,1,n) lf[i]=(d[i]==1);
64 FOR(i,1,n) if (!lf[i]) {rt=i;break;}
65 if (dfs(rt,0)) yes();
66 no();
67 return 0;
68 }