#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
const int nx=5e4+5;
int n, c[nx], sz[nx], dp[nx], pa[nx], vs[nx];
vector<int> d[nx];
int dfssz(int u, int p)
{
sz[u]=1;
for (auto v:d[u]) if (v!=p) sz[u]+=dfssz(v, u);
return sz[u];
}
void findcentroid(int u, int p, int rtsz)
{
for (auto v:d[u]) if (v!=p&&2*sz[v]>=rtsz) return findcentroid(v, u, rtsz);
c[u]=1;
c[p]=(2*sz[u]<=rtsz);
pa[u]=p;
pa[p]=u;
}
void dfs(int u, int p, int safe)
{
sz[u]=1;
if (safe==u) dp[u]=1;
if (u!=p) pa[u]=p;
for (auto v:d[u]) if (v!=p&&!c[v]) dfs(v, u, safe), dp[u]|=dp[v], sz[u]+=sz[v];
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
n=F.size()+1;
for (int i=1; i<=n; i++) d[i].clear(), c[i]=dp[i]=sz[i]=0;
for (auto [u, v]:F) d[u].push_back(v), d[v].push_back(u);
findcentroid(1, 1, dfssz(1, 1));
for (int i=1; i<=n; i++) if (c[i]) dfs(i, i, safe);
vector<int> res;
for (int i=1; i<=n; i++) res.push_back(dp[i]);
return res;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
n=F.size()+1;
for (int i=1; i<=n; i++) d[i].clear(), c[i]=dp[i]=sz[i]=pa[i]=vs[i]=0;
for (auto [u, v]:F) d[u].push_back(v), d[v].push_back(u);
findcentroid(1, 1, dfssz(1, 1));
for (int i=1; i<=n; i++) if (c[i]) dfs(i, i, 0);
while (1)
{
vs[curr]=1;
if (t==0) t=visit(pa[curr]), curr=pa[curr];
else
{
vector<pair<int, int>> hv;
for (auto v:d[curr]) if (v!=pa[curr]) hv.push_back({sz[v], v});
sort(hv.begin(), hv.end());
reverse(hv.begin(), hv.end());
int f=1;
for (auto [sz, v]:hv)
{
if (vs[v]) continue;
auto nt=visit(v);
if (nt)
{
f=0;
curr=v;
t=nt;
break;
}
visit(curr);
}
if (f) return;
}
}
}
/*
5 4
1 2
2 4
2 3
4 5
*/
