#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> adj;
vector<int> parent;
vector<int> depth;
vector<int> subtree_size;
void dfs(int from, int d = 0) {
depth[from] = d;
for (int j: adj[from]) {
if (j == parent[from]) continue;
parent[j] = from;
dfs(j, d + 1);
subtree_size[from] += subtree_size[j];
}
}
int find_center(int treasure_pos) {
parent.assign(n, -1);
depth.assign(n, -1);
subtree_size.assign(n, 0);
dfs(treasure_pos);
int end1 = 0;
for (int i = 1; i < n; ++i)
if (depth[i] > depth[end1]) end1 = i;
parent[end1] = -1;
dfs(end1);
int end2 = 0;
for (int i = 1; i < n; ++i)
if (depth[i] > depth[end2]) end2 = i;
int center = end2;
while (depth[center] * 2 > depth[end2] + 1) center = parent[center];
subtree_size.assign(n, 1);
parent[center] = -1;
dfs(center);
return center;
}
void to_adj_list(const vector<pair<int, int>>& edges) {
n = edges.size() + 1;
adj.assign(n, {});
for (auto [a, b]: edges) {
--a;
--b;
adj[a].push_back(b);
adj[b].push_back(a);
}
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
--safe;
to_adj_list(F);
find_center(safe);
vector<int> ties(n, 0);
do {
ties[safe] = 1;
safe = parent[safe];
} while (safe != -1);
return ties;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
--curr;
to_adj_list(F);
find_center(0);
while (t == 0 && parent[curr] != -1) {
curr = parent[curr];
assert(curr != -1);
t = visit(curr + 1);
}
for (;;) {
sort(adj[curr].begin(), adj[curr].end(), [&](int a, int b){ return subtree_size[a] > subtree_size[b]; });
bool found = false;
for (int j: adj[curr]) {
if (j == parent[curr]) continue;
t = visit(j + 1);
if (t) {
found = true;
curr = j;
break;
}
t = visit(curr + 1);
}
if (!found) return;
}
}
