#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
const int nmax = 1e5;
int n;
vector<int> G[nmax + 5];
int w[nmax + 5];
vector<int> t;
int d[nmax + 5];
bool sel[nmax + 5];
void get_w_mark(int nod, int dad = 0)
{
w[nod] = 1;
for(auto it : G[nod])
{
if(it == dad)
{
continue;
}
get_w_mark(it, nod);
w[nod] += w[it];
}
}
void get_mark(int nod, int dad = 0)
{
int Max = 0;
for(auto it : G[nod])
{
if(it == dad)
{
continue;
}
get_mark(it, nod);
if(w[it] > w[Max])
{
Max = it;
}
}
if(n - w[nod] >= w[Max])
{
t[nod - 1] = 1;
}
}
vector<int> mark(vector<pair<int,int>> e, int root)
{
n = e.size() + 1;
t.resize(n);
for(auto it : e)
{
G[it.first].push_back(it.second);
G[it.second].push_back(it.first);
}
get_w_mark(root);
get_mark(root);
return t;
}
void get_w_locate(int nod, int dad = 0)
{
d[nod] = dad;
w[nod] = 1;
for(auto it : G[nod])
{
if(it == dad)
{
continue;
}
get_w_locate(it, nod);
w[nod] += w[it];
}
}
void locate(vector<pair<int,int>> e, int start, int val)
{
n = e.size() + 1;
for(int i=1;i<=n;i++)
{
G[i].clear();
}
for(auto it : e)
{
G[it.first].push_back(it.second);
G[it.second].push_back(it.first);
}
get_w_locate(start);
int nod = start;
while(!sel[nod])
{
sel[nod] = true;
vector<pair<int,int>> l;
for(auto it : G[nod])
{
if(it == d[nod])
{
l.push_back({n - w[nod], it});
}
else
{
l.push_back({w[it], it});
}
}
sort(l.begin(), l.end(), greater<pair<int,int>>());
if(val == 1)
{
if(l.size() == 1)
{
val = visit(l.front().second);
nod = l.front().second;
}
else
{
if(l[0].first > l[1].first)
{
val = visit(l[0].second);
nod = l[0].second;
}
else
{
val = visit(l[0].second);
if(val == 1)
{
val = visit(nod);
val = visit(l[1].second);
nod = l[1].second;
}
else
{
nod = l[0].second;
}
}
}
}
else
{
if(l.size() == 2)
{
val = visit(l[1].second);
nod = l[1].second;
}
else
{
val = visit(l[1].second);
if(val == 1)
{
val = visit(nod);
val = visit(l[2].second);
nod = l[2].second;
}
else
{
nod = l[1].second;
}
}
}
}
}
