#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int N_MAX = 2e5;
const int K_MAX = 1e6;
struct defEdge {
int from, to, cost;
}; vector<defEdge> tree[1 + N_MAX];
int n, k; int sizOf[1 + N_MAX];
int64 preffSum[1 + N_MAX]; int depth[1 + N_MAX];
void auxDFS (int root, int p, int cost) {
preffSum[root] = preffSum[p] + cost;
depth[root] = depth[p] + 1;
for (defEdge e : tree[root])
if (e.to != p)
auxDFS (e.to, root, e.cost);
sizOf[root] = 1;
for (defEdge e : tree[root])
sizOf[root] += sizOf[e.to];
}
const int NONE = -1;
map<int64, int> minDist; /// minDist[k] = numarul minim de muchii cu distanta k
vector<int> subTree[1 + N_MAX];
int answer[1 + N_MAX]; /// answer[root] = numarul minim de muchii care trec prin root cu suma k
void DFS (int root, int p, bool toEliminate) {
int maxSize = 0, heavyChild = NONE;
for (defEdge e : tree[root])
if (e.to != p && sizOf[e.to] > maxSize)
maxSize = sizOf[e.to], heavyChild = e.to;
for (defEdge e : tree[root])
if (e.to != p && e.to != heavyChild)
DFS (e.to, root, true);
if (heavyChild != NONE) {
DFS (heavyChild, root, false);
swap (subTree[root], subTree[heavyChild]);
}
int64 target = k + 2 * preffSum[root];
subTree[root].push_back (root);
minDist[preffSum[root]] = depth[root];
if (minDist[target - preffSum[root]])
answer[root] = minDist[target - preffSum[root]] - minDist[preffSum[root]];
for (defEdge e : tree[root]) {
if (e.to != p && e.to != heavyChild) {
for (int aux : subTree[e.to])
if (minDist[target - preffSum[aux]])
answer[root] = min (answer[root], minDist[target - preffSum[aux]] + depth[aux] - 2 * depth[root]);
for (int aux : subTree[e.to]) {
subTree[root].push_back (aux);
if (!minDist[preffSum[aux]] || minDist[preffSum[aux]] > depth[aux])
minDist[preffSum[aux]] = depth[aux];
}
}
}
if (toEliminate)
for (int aux : subTree[root])
minDist[preffSum[aux]] = 0;
}
const int PAIR = 2;
int best_path (int N, int K, int H[][PAIR], int L[]) {
n = N, k = K;
for (int i = 0; i < n - 1; i ++) {
int u = H[i][0], v = H[i][1]; u ++, v ++;
tree[u].push_back ({u, v, L[i]});
tree[v].push_back ({v, u, L[i]});
}
depth[0] = NONE, preffSum[0] = 0; auxDFS (1, 0, 0);
for (int node = 1; node <= n; node ++)
answer[node] = 1 + N_MAX;
DFS (1, 0, true);
int miny = answer[1];
for (int node = 2; node <= n; node ++)
miny = min (miny, answer[node]);
if (miny == 1 + N_MAX)
return NONE;
return miny;
}
/**void TestOut (void) {
cin >> n >> k;
for (int i = 1; i < n; i ++) {
int u, v, cost; cin >> u >> v >> cost; u ++, v ++;
tree[u].push_back ({u, v, cost});
tree[v].push_back ({v, u, cost});
}
depth[0] = NONE, preffSum[0] = 0; auxDFS (1, 0, 0);
for (int node = 1; node <= n; node ++)
cout << depth[node] << " " << preffSum[node] << "\n";
for (int node = 1; node <= n; node ++)
answer[node] = 1 + N_MAX;
DFS (1, 0, true);
int miny = answer[1];
for (int node = 2; node <= n; node ++)
miny = min (miny, answer[node]);
if (miny == 1 + N_MAX)
cout << NONE;
else
cout << miny;
}**/
/**int main()
{
/// TestOut ();
return 0;
}**/
