#include <vector> #include <iostream> #include "grader.h" using namespace std; const int MAXN = 512; vector<int> g[MAXN + 1], toquery; vector<vector<int>> subtrees; int viz[MAXN + 1], sz[MAXN + 1], answer; void dfsSize(int node, int parent) { sz[node] = 1; for(int son : g[node]) { if(!viz[son] && son != parent) { dfsSize(son, node); sz[node] += sz[son]; } } } int findCentroid(int node, int limit) { for(int son : g[node]) { if(!viz[son] && sz[son] < sz[node] && sz[son] > limit) { return findCentroid(son, limit); } } return node; } void dfs(int node, int parent) { subtrees.back().push_back(node); for(int son : g[node]) { if(!viz[son] && son != parent) { dfs(son, node); } } } void decompose(int node) { dfsSize(node, 0); node = findCentroid(node, sz[node] / 2); subtrees = {{node}}; for(int son : g[node]) { if(!viz[son]) { subtrees.push_back({}); dfs(son, node); } } int st = 0, dr = (int)subtrees.size() - 1, poz = 0; while(st <= dr) { int mij = (st + dr) / 2; toquery.clear(); for(int i = 0; i <= mij; i++) { for(int node : subtrees[i]) { toquery.push_back(node); } } if(query(toquery)) { poz = mij; dr = mij - 1; } else { st = mij + 1; } } if(poz == 0) { answer = node; return; } viz[node] = 1; int cnt = 0; for(int son : g[node]) { if(!viz[son]) { cnt++; if(cnt == poz) { decompose(son); return; } } } } int findEgg(int n, vector<pair<int, int>> edges) { for(int i = 1; i <= n; i++) { g[i].clear(); viz[i] = 0; } for(int i = 0; i < n - 1; i++) { g[edges[i].first].push_back(edges[i].second); g[edges[i].second].push_back(edges[i].first); } decompose(1); return answer; }