제출 #253985

#제출 시각아이디문제언어결과실행 시간메모리
253985BertedTax Evasion (LMIO19_mokesciai)C++14
100 / 100
196 ms72192 KiB
#include <iostream>
#include <set>
#include <vector>
#include <assert.h>
#include <map>
#include <list>
#define vi vector<int>
#define pub push_back
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;

int n, k, cnt[200001] = {}, mn = 1e9;
bool spc[200001];
list<int> adj[200001];
vi par;

void dfs(int u, int p)
{
	int h = par.size();
	par.push_back(u);
	cnt[par[h / 2 + 1]] += spc[u];
	spc[u] = 0;
	for (auto v : adj[u])
	{
		// cout << u << " - " << v << "\n";
		if (v != p) dfs(v, u);
	}
	par.pop_back();
}


map<int, int>* dfs2(int u, int p, int h)
{
	map<int, int>* ret = new map<int, int>;
	map<int, int>* rr;
	(*ret)[-h]++;
	for (auto v : adj[u])
	{
		if (v != p)
		{
			rr = dfs2(v, u, h + 1);
			if (rr -> size() > ret -> size()) {swap(rr, ret);}
			for (auto v : *rr) {(*ret)[v.fst] += v.snd;}
		}
	}
	for (int i = 0; i < cnt[u]; i++)
	{
		mn = min(mn, -(ret -> begin() -> fst));
		(ret -> begin() -> snd)--;
		if (ret -> begin() -> snd == 0) {ret -> erase(ret -> begin());}
	}
	return ret;
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		int v; cin >> v;
		adj[v - 1].push_back(i);
		adj[i].push_back(v - 1);
	}
	for (int i = 0; i < k; i++)
	{
		int x; cin >> x; spc[x - 1] = 1;
	}
	if (spc[0]) {cout << "1\n";}
	else
	{
		dfs(0, -1); dfs2(0 ,-1, 0);
		cout << mn + 1 << '\n';
	}
	
	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...