#include "split.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<int> edge[100005];
vector<int> treeEdge[100005];
bool visited[100005];
int cent;
int val[100005];
int treeSize[100005];
int treeNum[100005];
int parent[100005];
void dfs(int root)
{
visited[root] = true;
for (auto& e : edge[root])
{
if (visited[e])
continue;
treeEdge[root].push_back(e);
treeEdge[e].push_back(root);
dfs(e);
}
}
int findCent(int root, int n)
{
treeSize[root] = 1;
bool isCent = true;
for (auto& e : treeEdge[root])
{
if (e == parent[root])
continue;
parent[e] = root;
int c = findCent(e, n);
if (c != -1)
return c;
treeSize[root] += treeSize[e];
isCent = isCent && (treeSize[e] < (n + 1) / 2);
}
if (isCent && treeSize[root] >= (n + 1) / 2)
return root;
return -1;
}
void numbering(int root, int k)
{
treeNum[root] = k;
for (auto& e : edge[root])
{
if (treeNum[e] != 0)
continue;
numbering(e, k);
}
}
int comp(int root)
{
// cent 방향 안 가면서 크기 계산, 트리 번호도 붙여준다
int res = 1;
visited[root] = true;
for (auto& e : edge[root])
{
if (visited[e] || e == cent)
continue;
res += comp(e);
}
return res;
}
void mark(int root, int v, int& c)
{
if (c == 0)
return;
val[root] = v;
c--;
// 같은 트리 우선으로 순회
for (auto& e : edge[root])
{
if (val[e] != 0 || treeNum[v] != treeNum[root])
continue;
mark(e, v, c);
}
for (auto& e : edge[root])
{
if (val[e] != 0)
continue;
mark(e, v, c);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
vector<ii> v = { { a, 1 }, { b, 2 }, { c, 3 } };
for (int i = 0; i < p.size(); i++)
{
edge[p[i]].push_back(q[i]);
edge[q[i]].push_back(p[i]);
}
dfs(0);
sort(all(v));
cent = findCent(0, n);
// centroid 제외한 그래프에서 a이상의 크기인 트리가 있는지 확인, 있으면 go
memset(visited, false, sizeof(visited));
int tr = 1;
for (auto& e : edge[cent])
{
numbering(e, tr);
tr++;
}
for (auto& e : edge[cent])
{
int sz = comp(e);
if (sz < v[0].xx)
continue;
val[cent] = v[1].yy;
mark(e, v[0].yy, v[0].xx);
mark(cent, v[1].yy, v[1].xx);
for (int i = 0; i < n; i++)
if (val[i] == 0)
val[i] = v[2].yy;
break;
}
vector<int> result(n);
for (int i = 0; i < n; i++)
result[i] = val[i];
return result;
}
