#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
const int MAX_N = 4.5e4;
bool vis[MAX_N + 1];
int sizee[MAX_N + 1], parent[MAX_N + 1];
vector<int> adj[MAX_N + 1];
void calcSizes( int u, int p ) {
sizee[u] = 1;
for ( int v: adj[u] ) {
if ( v == p )
continue;
calcSizes( v, u );
sizee[u] += sizee[v];
}
}
int n;
vector<int> centroids;
void findCentroids( int u, int p ) {
int maxSize = n - sizee[u];
for ( int v: adj[u] ) {
if ( v == p )
continue;
findCentroids( v, u );
maxSize = max( maxSize, sizee[v] );
}
if ( maxSize <= n / 2 )
centroids.push_back( u );
}
vector<int> ties;
void assignTies( int u, int p, int safe ) {
if ( u == safe )
ties[u - 1] = 1;
for ( int v: adj[u] ) {
if ( v == p )
continue;
assignTies( v, u, safe );
ties[u - 1] += ties[v - 1];
}
}
void calcParents( int u, int p ) {
parent[u] = p;
for ( int v: adj[u] ) {
if ( v == p )
continue;
calcParents( v, u );
}
}
vector<int> mark( vector<pair<int, int>> F, int safe ) {
n = F.size() + 1;
centroids.clear();
for ( int v = 1; v <= n; v++ )
adj[v].clear(), sizee[v] = 0;
for ( int i = 0; i < F.size(); i++ ) {
adj[F[i].first].push_back( F[i].second );
adj[F[i].second].push_back( F[i].first );
}
calcSizes( 1, 0 );
findCentroids( 1, 0 );
ties.clear();
ties.resize( n );
assignTies( centroids[0], 0, safe );
return ties;
}
void locate( vector<std::pair<int, int>> F, int curr, int t ) {
n = F.size() + 1;
centroids.clear();
for ( int v = 1; v <= n; v++ )
adj[v].clear(), sizee[v] = 0;
for ( int i = 0; i < F.size(); i++ ) {
adj[F[i].first].push_back( F[i].second );
adj[F[i].second].push_back( F[i].first );
}
calcSizes( 1, 0 );
findCentroids( 1, 0 );
if ( centroids.size() == 2 )
swap( centroids[0], centroids[1] );
calcParents( centroids[0], 0 );
calcSizes( centroids[0], 0 );
int v = curr;
while ( 1 ) {
vis[v] = true;
if ( t == 0 ) {
if ( parent[v] == 0 ) {
parent[centroids[0]] = centroids[1];
parent[centroids[1]] = centroids[0];
}
v = parent[v];
t = visit( v );
} else {
int maxSz = -1, nxt = -1;
for ( int u: adj[v] ) {
if ( (u != parent[v] || u == centroids[0]) && !vis[u] && sizee[u] >= maxSz ) {
nxt = u;
maxSz = u;
}
}
if ( nxt == -1 )
return;
v = nxt;
t = visit( v );
}
}
}
