#include "incursion.h"
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
namespace A {
const int N = 45000;
int ej[N][3], eo[N], n;
void append(int i, int j) {
ej[i][eo[i]++] = j;
}
void init(vpi ij) {
n = ij.size() + 1;
memset(eo, 0, n * sizeof *eo);
for (int h = 0; h < n - 1; h++) {
int i = ij[h].first - 1, j = ij[h].second - 1;
append(i, j), append(j, i);
}
}
int pp[N], sz[N], c1, c2;
void dfs1(int p, int i) {
sz[i] = 1;
bool centroid = true;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs1(i, j);
sz[i] += sz[j];
if (sz[j] * 2 > n)
centroid = false;
}
}
if ((n - sz[i]) * 2 > n)
centroid = false;
if (centroid) {
if (c1 == -1)
c1 = i;
else
c2 = i;
}
}
void dfs2(int p, int i) {
pp[i] = p;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs2(i, j);
}
}
}
vi mark(vpi ij, int t) {
A::init(ij), t--;
A::c1 = A::c2 = -1, A::dfs1(-1, t);
if (A::c2 == -1)
A::dfs2(-1, A::c1);
else
A::dfs2(A::c2, A::c1), A::dfs2(A::c1, A::c2);
vi cc(A::n, 0);
while (t != A::c1 && t != A::c2)
cc[t] = 1, t = A::pp[t];
cc[t] = 1;
return cc;
}
namespace B {
const int N = 45000;
int ej[N][3], eo[N], n;
void append(int i, int j) {
ej[i][eo[i]++] = j;
}
void init(vpi ij) {
n = ij.size() + 1;
memset(eo, 0, n * sizeof *eo);
for (int h = 0; h < n - 1; h++) {
int i = ij[h].first - 1, j = ij[h].second - 1;
append(i, j), append(j, i);
}
}
int pp[N], sz[N], c1, c2;
void dfs1(int p, int i) {
sz[i] = 1;
bool centroid = true;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs1(i, j);
sz[i] += sz[j];
if (sz[j] * 2 > n)
centroid = false;
}
}
if ((n - sz[i]) * 2 > n)
centroid = false;
if (centroid) {
if (c1 == -1)
c1 = i;
else
c2 = i;
}
}
void dfs2(int p, int i) {
pp[i] = p;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs2(i, j);
}
}
}
void locate(vpi ij, int s, int c) {
B::init(ij), s--;
B::c1 = B::c2 = -1, B::dfs1(-1, s);
if (B::c2 == -1)
B::dfs2(-1, B::c1);
else
B::dfs2(B::c2, B::c1), B::dfs2(B::c1, B::c2);
int i = s, q = -1;
while (c == 0)
q = i, c = visit((i = B::pp[i]) + 1);
while (1) {
int j1 = -1, j2 = -1, j3 = -1, tmp;
for (int o = B::eo[i]; o--; ) {
int j = B::ej[i][o];
if (j != B::pp[i] && j != q) {
if (j1 == -1)
j1 = j;
else if (j2 == -1)
j2 = j;
else
j3 = j;
}
}
if (j1 == -1 || j2 != -1 && B::sz[j1] < B::sz[j2])
tmp = j1, j1 = j2, j2 = tmp;
if (j1 == -1 || j3 != -1 && B::sz[j1] < B::sz[j3])
tmp = j1, j1 = j3, j3 = tmp;
if (j2 == -1 || j3 != -1 && B::sz[j2] < B::sz[j3])
tmp = j2, j2 = j3, j3 = tmp;
if (j1 != -1) {
if (visit(j1 + 1)) {
i = j1;
continue;
}
visit(i + 1);
}
if (j2 != -1) {
if (visit(j2 + 1)) {
i = j2;
continue;
}
visit(i + 1);
}
if (j3 != -1) {
if (visit(j3 + 1)) {
i = j3;
continue;
}
visit(i + 1);
}
break;
}
}
