Submission #2167589

---

Source Code Expand

#include <iostream>
#include <vector>
#include <utility>
#define inf 1000000000

using namespace std;

struct edge{
	int to, cap, rev;
	edge(int a, int b, int c){
		to = a, cap = b, rev = c;
	}
};

int N;
vector<int> tree[100005];
int depth[100005];
vector<edge> G[100005];
int S, T;
bool used[100005];

void dfs2(int v, int prev, int dep)
{
	depth[v] = dep;
	for(int i = 0; i < tree[v].size(); i++){
		if(tree[v][i] != prev) dfs2(tree[v][i], v, dep+1);
	}
}

int dfs(int v, int f)
{
	used[v] = true;
	if(v == T) return f;
	
	int ret;
	for(int i = 0; i < G[v].size(); i++){
		if(used[G[v][i].to] || G[v][i].cap <= 0) continue;
		ret = dfs(G[v][i].to, min(f, G[v][i].cap));
		if(ret > 0){
			G[v][i].cap -= ret;
			G[G[v][i].to][G[v][i].rev].cap += ret;
			return ret;
		}
	}
	return 0;
}

void add_edge(int s, int t, int cap)
{
	G[s].push_back(edge(t, cap, G[t].size()));
	G[t].push_back(edge(s, 0, G[s].size()-1));
}

int main(void)
{
	cin >> N;
	int a, b;
	for(int i = 0; i < N-1; i++){
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	S = N+1, T = N+2;
	
	dfs2(1, -1, 0);
	for(int i = 1; i <= N; i++){
		if(depth[i] % 2){
			add_edge(S, i, 1);
			for(int j = 0; j < tree[i].size(); j++) add_edge(i, tree[i][j], 1);
		}
		else add_edge(i, T, 1);
	}
	
	int ans = 0, flow;
	while(1){
		for(int i = 1; i <= T; i++) used[i] = false;
		flow = dfs(S, inf);
		if(flow <= 0) break;
		ans += flow;
	}
	
	if(N % 2 == 0 && ans == N/2) cout << "Second" << endl;
	else cout << "First" << endl;
	return 0;
}

Submission Info

Judge Result