#include "closing.h"
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 200000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *ej[N], *ew[N], eo[N];
void append(int i, int j, int w) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0) {
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
}
ej[i][o] = j, ew[i][o] = w;
}
int pp[N]; long long *dd; char path[N];
long long dds[N], ddt[N]; int ii[N];
long long dd1[N * 2]; int ii1[N * 2], n1;
long long dda2[N], ddb2[N]; int ii2[N], n2;
long long dp1[N * 2 + 1], dp2[N * 2 + 1];
void dfs(int p, int i, long long d) {
pp[i] = p, dd[i] = d;
for (int o = eo[i]; o--; ) {
int j = ej[i][o], w = ew[i][o];
if (j != p)
dfs(i, j, d + w);
}
}
int compare_ds(int i, int j) {
return dds[i] == dds[j] ? 0 : (dds[i] < dds[j] ? -1 : 1);
}
int compare_d1(int i, int j) {
return dd1[i] == dd1[j] ? 0 : (dd1[i] < dd1[j] ? -1 : 1);
}
int compare_db2(int i, int j) {
return ddb2[i] == ddb2[j] ? 0 : (ddb2[i] < ddb2[j] ? -1 : 1);
}
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int max_score(int n, int s, int t, long long c_, vi uu, vi vv, vi ww) {
for (int i = 0; i < n; i++) {
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
ew[i] = (int *) malloc(2 * sizeof *ew[i]);
eo[i] = 0;
}
for (int h = 0; h < n - 1; h++)
append(uu[h], vv[h], ww[h]), append(vv[h], uu[h], ww[h]);
dd = dds, dfs(-1, s, 0);
dd = ddt, dfs(-1, t, 0);
for (int i = 0; i < n; i++)
if (dds[i] > ddt[i]) {
long long tmp;
tmp = dds[i], dds[i] = ddt[i], ddt[i] = tmp;
}
for (int i = 0; i < n; i++)
ii[i] = i;
compare = compare_ds, sort(ii, 0, n);
int k = 0; long long c = 0;
while (k < n && c + dds[ii[k]] <= c_)
c += dds[ii[k++]];
memset(path, 0, n * sizeof *path);
for (int i = s; i != -1; i = pp[i])
path[i] = 1;
int k0 = 0; n1 = 0, n2 = 0;
for (int i = 0; i < n; i++)
if (path[i]) {
c_ -= dds[i], k0++;
dd1[n1++] = ddt[i] - dds[i];
} else if (dds[i] <= ddt[i] - dds[i])
dd1[n1++] = dds[i], dd1[n1++] = ddt[i] - dds[i];
else
dda2[n2] = dds[i], ddb2[n2] = ddt[i], n2++;
if (c_ >= 0) {
for (int i = 0; i < n1; i++)
ii1[i] = i;
compare = compare_d1, sort(ii1, 0, n1);
memset(dp1, 0x3f, (n1 + 1) * sizeof *dp1), dp1[0] = 0;
for (int i = 0; i < n1; i++)
dp1[i + 1] = dp1[i] + dd1[ii1[i]];
for (int i = 0; i < n2; i++)
ii2[i] = i;
compare = compare_db2, sort(ii2, 0, n2);
memset(dp2, 0x3f, (n2 * 2 + 1) * sizeof *dp2), dp2[0] = 0;
long long b = 0, d = 0;
for (int i = 0; i < n2; i++) {
d = max(d, ddb2[ii2[i]] - dda2[ii2[i]]), b += ddb2[ii2[i]];
dp2[(i + 1) * 2] = b;
dp2[(i + 1) * 2 - 1] = b - d;
}
long long a = INF;
for (int i = n2 - 1; i >= 0; i--) {
a = min(a, dda2[ii2[i]]), b -= ddb2[ii2[i]];
dp2[i * 2 + 1] = min(dp2[i * 2 + 1], b + a);
}
for (int k1 = 0, k2 = n2 * 2; k1 <= n1; k1++) {
while (k2 >= 0 && dp1[k1] + dp2[k2] > c_)
k2--;
if (k2 >= 0)
k = max(k, k0 + k1 + k2);
}
}
for (int i = 0; i < n; i++)
free(ej[i]), free(ew[i]);
return k;
}
