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 }