제출 #118340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
118340		teomrn	Mousetrap (CEOI17_mousetrap)	C++14	45 / 100	1229 ms	81308 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1000010;
vector <int> adia[NMAX];
int cost[NMAX];
int tata[NMAX];
int h[NMAX];
int nr_op;

void dfs(int nod, int t)
{
	if (t)
		adia[nod].erase(find(adia[nod].begin(), adia[nod].end(), t));
	tata[nod] = t;
	h[nod] = 1 + h[t];

	for (auto i : adia[nod])
		dfs(i, nod);
}

void calc_cost(int nod)
{
	for (auto i : adia[nod])
		calc_cost(i);

	int max1 = 0, max2 = 0;
	for (auto i : adia[nod]) {
		if (cost[i] > max1)
			max2 = max1, max1 = cost[i];
		else if (cost[i] > max2)
			max2 = cost[i];
	}

	cost[nod] = adia[nod].size() + max2;
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, root, x;
	cin >> n >> root >> x;

	if (root == x) {
		cout << "0\n";
		return 0;
	}

	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adia[a].push_back(b);
		adia[b].push_back(a);
	}

	dfs(root, 0);
	calc_cost(x);

	int ans = cost[x];
	x = tata[x];

	while (x != root) {
		ans += adia[x].size() - 1;
		x = tata[x];
	}

	cout << ans << '\n';

	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35