#include "race.h"
#include <vector>
#include <map>
#include <climits>
#include <iostream>
#ifndef maxn
#define maxn 200005
using namespace std;
typedef long long ll;
struct edge {
int to;
ll w;
edge() {
}
edge(int t, int w_) {
to = t;
w = w_;
}
};
vector<edge> adjList[maxn];
int subtreeSize[maxn];
map<ll, int>* sack[maxn]; // Holds pairs (distance to root, min edges to root)
// cannot hold (distance to current node, min edges to current node) since these are relative and would have to be updated
int k; // Searched dist
int minimum; // Answer, minimum number of edges
void update(int u, ll dist, int depth) {
if ((*sack[u]).find(dist) == (*sack[u]).end())
(*sack[u])[dist] = INT_MAX;
(*sack[u])[dist] = min((*sack[u])[dist], depth);
}
void printSack(int u) {
cout << "Sack of " << u << endl;
for (pair<ll, int> p : *sack[u]) {
cout << p.first << " " << p.second << endl;
}
cout << endl;
}
void search(int u, int p, int greatestChild, int depth, ll dist) {
for (edge e : adjList[u]) {
int v = e.to;
ll w = e.w;
if (v == p || v == greatestChild) continue;
for (pair<ll, int> curEndpoint : *sack[v]) {
ll curDist = curEndpoint.first - dist;
int curEdges = curEndpoint.second - depth;
// Search for the complement
int complement = k - curDist;
int searchedComplement = complement + dist;
if ((*sack[u]).find(searchedComplement) != (*sack[u]).end()) {
// Found two-part path
int edges = curEdges + (*sack[u])[searchedComplement] - depth;
minimum = min(minimum, edges);
}
}
// Copy information from this child in order to allow others to find routes to already computed child
for (pair<ll, int> curEndpoint : *sack[v]) {
update(u, curEndpoint.first, curEndpoint.second);
}
}
int searchedDist = k + dist;
if ((*sack[u]).find(searchedDist) != (*sack[u]).end()) { // Found one-part path
int realEdgesCnt = (*sack[u])[searchedDist] - depth; // Edges relative to this node
minimum = min(minimum, realEdgesCnt);
}
}
void dfs(int u, int p, int depth, ll dist) {
subtreeSize[u] = 1;
int maxSubtreeSize = 0, greatestChild = -1;
for (edge e : adjList[u]) {
int v = e.to;
ll w = e.w;
if (v == p) continue;
dfs(v, u, depth + 1, dist + w);
subtreeSize[u] += subtreeSize[v];
if (subtreeSize[v] > maxSubtreeSize) {
maxSubtreeSize = subtreeSize[v];
greatestChild = v;
}
}
if (greatestChild == -1) {
// Leaf node
sack[u] = new map<ll, int>();
}
else {
sack[u] = sack[greatestChild];
}
search(u, p, greatestChild, depth, dist);
update(u, dist, depth);
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
minimum = INT_MAX;
for (int i = 0; i < N - 1; i++) {
int a = H[i][0] + 1;
int b = H[i][1] + 1;
ll w = L[i];
adjList[a].push_back(edge(b, w));
adjList[b].push_back(edge(a, w));
}
dfs(1, 0, 0, 0);
return (minimum == INT_MAX? -1 : minimum);
}
#endif
