#include "race.h"
#include <stdlib.h>
#include <string.h>
#define N 200000
#define L 1000000
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int ij[N - 1], ww[N - 1];
int *eh[N], eo[N];
void append(int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
eh[i][o] = h;
}
int sz[N], c;
void dfs0(int p, int i, int n) {
int o, centroid;
sz[i] = 1, centroid = 1;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ij[h];
if (j != p) {
dfs0(i, j, n);
if (sz[j] * 2 > n)
centroid = 0;
sz[i] += sz[j];
}
}
if ((n - sz[i]) * 2 > n)
centroid = 0;
if (centroid)
c = i;
}
int xx[N], dd[N], dd_[L + 1], qu[N], l, cnt, ans;
void dfs1(int p, int i, int x, int d) {
int o;
xx[i] = x, dd[i] = d;
if (x <= l)
ans = min(ans, dd_[l - x] + d);
qu[cnt++] = i;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ij[h];
if (j != p)
dfs1(i, j, min(x + ww[h], l + 1), d + 1);
}
}
void delete(int i, int h) {
int o;
for (o = eo[i]; o--; )
if (eh[i][o] == h) {
eo[i]--;
while (o < eo[i])
eh[i][o] = eh[i][o + 1], o++;
return;
}
}
void cd(int i, int n) {
int o, g;
dfs0(-1, i, n), i = c;
cnt = 0;
xx[i] = 0, dd[i] = 0;
qu[cnt++] = i, dd_[xx[i]] = dd[i];
for (o = eo[i], g = 0; o--; ) {
int h = eh[i][o], j = i ^ ij[h];
delete(j, h);
dfs1(i, j, min(ww[h], l + 1), 1);
while (g < cnt) {
j = qu[g++];
if (xx[j] <= l)
dd_[xx[j]] = min(dd_[xx[j]], dd[j]);
}
}
while (cnt--) {
int j = qu[cnt];
if (xx[j] <= l)
dd_[xx[j]] = INF;
}
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ij[h];
cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i]);
}
}
int best_path(int n, int l_, int ii_[][2], int *ww_) {
int h, i, j;
memcpy(ww, ww_, (n - 1) * sizeof *ww_), l = l_;
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (h = 0; h < n - 1; h++) {
i = ii_[h][0], j = ii_[h][1];
ij[h] = i ^ j;
append(i, h), append(j, h);
}
memset(dd_, 0x3f, (l + 1) * sizeof *dd_);
ans = INF;
cd(0, n);
if (ans == INF)
ans = -1;
return ans;
}
