// g++ -std=c++17 grader.cpp incursion.cpp -o incursion
#include<bits/stdc++.h>
#include "incursion.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MAXN = 45e3+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int sub[MAXN], pai[MAXN], n;
vector<vi> edges;
void calc_sub(int x) {
sub[x] = 1;
for(auto viz : edges[x]) {
if(viz == pai[x]) continue;
pai[viz] = x;
calc_sub(viz);
sub[x] += sub[viz];
}
}
vi find_centroid(int x) {
for(auto viz : edges[x]) {
if(viz == pai[x]) continue;
if(2*sub[viz] >= n)
return find_centroid(viz);
}
if(sub[x]*2 == n) return {pai[x], x};
return {x};
}
vi mark(vector<pii> F, int safe) {
n = sz(F)+1;
pai[1] = 0;
edges.clear();
edges.resize(n+1);
for(auto [a, b] : F)
edges[a].pb(b), edges[b].pb(a);
calc_sub(1);
vi c = find_centroid(1);
int m = sz(c)-1;
pai[c[0]] = c[m];
pai[c[m]] = c[0];
calc_sub(c[0]);
calc_sub(c[m]);
vi ans(n);
while(true) {
ans[safe-1] = 1;
if(pai[pai[safe]] == safe) break;
safe = pai[safe];
}
return ans;
}
void locate(vector<pii> F, int curr, int ties) {
n = sz(F)+1;
pai[1] = 0;
edges.clear();
edges.resize(n+1);
for(auto [a, b] : F)
edges[a].pb(b), edges[b].pb(a);
calc_sub(1);
vi c = find_centroid(1);
int m = sz(c)-1;
pai[c[0]] = c[m];
pai[c[m]] = c[0];
calc_sub(c[0]);
calc_sub(c[m]);
// a partir daqui ja sabemos os pais de cada um
// e vamos subir
while(ties == 0) {
curr = pai[curr];
ties = visit(curr);
}
// ties = 1, agora descemos
while(true) {
vi v;
for(auto viz : edges[curr])
if(viz != pai[curr]) v.pb(viz);
if(v.empty()) break;
if(sub[v[0]] > sub[v.back()]) swap(v[0], v[1]);
int new_c = curr;
for(auto viz : v) {
ties = visit(viz);
if(ties == 1) {
new_c = viz;
break;
}
visit(curr);
}
if(new_c == curr) break;
else curr = new_c;
}
}
