제출 #1094646

#제출 시각아이디문제언어결과실행 시간메모리
1094646stefanneaguMousetrap (CEOI17_mousetrap)C++17
0 / 100
743 ms77888 KiB
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int nmax = 1e6 + 1;

int dp[nmax];

vector<int> adj[nmax];

void dfs(int i, int tata = 0) {
	int minn = 1e9;
	for(auto it : adj[i]) {
		if(it == tata) {
			continue;
		}
		dfs(it, i);
		minn = min(minn, dp[it]);
	}
	if(adj[i].size() == 1) {
		dp[i] = 0;
		return;
	}
	dp[i] = minn + adj[i].size() - 1;
}

int32_t main() {
	int n, ep, sp;
	cin >> n >> ep >> sp;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(ep);
	cout << dp[sp];
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...