#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 2e5 + 5;
int n, k;
basic_string <int> city[maxn];
basic_string <int> adj[maxn][2]; // One for each side of the edge
int siz[maxn][2] = { 0 };
bool removed[maxn] = { 0 };
int find_side(int p, int par)
{
auto it = lower_bound(adj[p][0].begin(), adj[p][0].end(), par);
return ((it == adj[p][0].end() || *it != par) + 1 ) & 1;
}
int calc_size(int p, int par, int subtree)
{
// Start
if (par == -1)
{
siz[p][0] = 0;
for (int i : adj[p][0])
{
if (removed[i]) continue;
siz[p][0] += calc_size(i, p, subtree) + 1;
}
siz[p][1] = 0;
for (int i : adj[p][1])
{
if (removed[i]) continue;
siz[p][1] += calc_size(i, p, subtree) + 1;
}
return 0;
}
int side = find_side(p, par);
siz[p][side] = 0;
for (int i : adj[p][side])
{
if (i == par) abort();
if (removed[i]) continue;
siz[p][side] += calc_size(i, p, subtree) + 1;
}
siz[p][(side + 1) & 1] = subtree - 1 - siz[p][side];
return siz[p][side];
}
int find_centroid(int p)
{
if (abs(siz[p][0] - siz[p][1]) <= 1) return p;
int side = (siz[p][0] < siz[p][1]);
for (int i : adj[p][side])
{
if (removed[i]) continue;
if (abs(siz[p][0] - siz[p][1]) < abs(siz[i][0] - siz[i][1])) continue;
return find_centroid(i);
}
return p;
}
vector <pii> scores[2];
void dfs(int p, int par, int val, int &max_val, int *l, int &side, int length)
{
length++;
val += l[p];
if (val > max_val) return ;
scores[side].emplace_back(pii(val, length));
if (par == -1)
{
for (int i : adj[p][0])
{
if (removed[i]) continue;
dfs(i, p, val, max_val, l, side, length + 1);
}
for (int i : adj[p][1])
{
if (removed[i]) continue;
dfs(i, p, val, max_val, l, side, length + 1);
}
return ;
}
int s = find_side(p, par);
for (int i : adj[p][s])
{
if (removed[i]) continue;
dfs(i, p, val, max_val, l, side, 0);
}
}
int output = 1e9;
void centroid_decomp(int centroid, int subtree, int *l)
{
removed[centroid] = true;
// Calculate
scores[0].clear();
scores[1].clear();
int nk = k - l[centroid];
scores[0].emplace_back(pii(0, 0));
scores[1].emplace_back(pii(0, 0));
for (int s = 0; s <= 1; s++) {
for (int i : adj[centroid][s])
{
if (removed[i]) continue;
dfs(i, -1, 0, nk, l, s, 0);
}
}
sort(scores[0].begin(), scores[0].end());
sort(scores[1].begin(), scores[1].end());
auto it = scores[0].begin();
auto rt = scores[1].rbegin();
while (it != scores[0].end() && rt != scores[1].rend())
{
if ((*it).first + (*rt).first == nk)
{
output = min(output, (*it).second + (*rt).second + 1);
it++;
} else if ((*it).first + (*rt).first < nk) it++;
else rt++;
}
// Left
for (int i : adj[centroid][0])
{
if (removed[i]) continue;
calc_size(i, -1, siz[centroid][0]);
centroid_decomp(find_centroid(i), siz[centroid][0], l);
break;
}
// Right
for (int i : adj[centroid][1])
{
if (removed[i]) continue;
calc_size(i, -1, siz[centroid][1]);
centroid_decomp(find_centroid(i), siz[centroid][1], l);
break;
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N - 1, k = K;
for (int i = 0; i < n; i++)
{
city[H[i][0]].push_back(i);
city[H[i][1]].push_back(i);
}
for (int i = 0; i < n; i++)
{
for (int y : city[H[i][0]])
{
if (y == i) continue;
adj[i][0].push_back(y);
}
for (int y : city[H[i][1]])
{
if (y == i) continue;
adj[i][1].push_back(y);
}
if (adj[i][0].size() > adj[i][1].size()) swap(adj[i][0], adj[i][1]); // Potentially very slow
sort(adj[i][0].begin(), adj[i][0].end());
// sort(adj[i][1].begin(), adj[i][1].end());
}
int p = 0;
calc_size(p, -1, n);
centroid_decomp(find_centroid(p), n, L);
cerr << clock() / static_cast<double>(CLOCKS_PER_SEC) << "\n";
return (output == 1e9 ? -1 : output);
}
