IOI '11 P2 - Race (Standard I/O)

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

const int INF = 1e9;

int n, k;
vector<vector<pair<int, int>>> g;
vector<bool> blockedNode;

vector<vector<int>> subtree; // depth, node
int findComponentCentroid(int node, int depth = 0) {
    // first find subtree sizes with node as root
    while ((int)subtree.size() <= depth) subtree.emplace_back(n);
    function<int(int, int)> getSubtree = [&](int v, int parent = -1) {
        subtree[depth][v] = 1;
        for (auto [u, w] : g[v]) {
            if (!blockedNode[u] && u != parent) subtree[depth][v] += getSubtree(u, v);
        }
        return subtree[depth][v];
    };
    int m = getSubtree(node, -1);

    int centroid = node;
    for (bool going = true; going; ) {
        going = false;
        for (auto [child, w] : g[centroid]) {
            if (subtree[depth][child] < subtree[depth][centroid] && 2*subtree[depth][child] > m) {
                going = true;
                centroid = child;
                break;
            }
        }
    }
    return centroid;
}

// Centroid Decomposition
int getComponentMin(int node, int depth = 0) { // shortest path of weight k in component of node
    vector<tuple<int, int, int>> paths; // weight, edges, component
    function<void(int, int, int, int, int)> findPaths = [&](int v, int parent, int direction, int distance, int edges) {
        paths.emplace_back(distance, edges, direction);
        for (auto [u, w] : g[v]) {
            if (!blockedNode[u] && u != parent) findPaths(u, v, direction, distance+w, edges+1);
        }
    };

    int centroid = findComponentCentroid(node, depth);
    for (auto [child, w] : g[centroid]) {
        if (!blockedNode[child]) findPaths(child, centroid, child, w, 1);
    };

    // Consider all paths containing centroid
    sort(paths.begin(), paths.end());
    vector<pair<pair<int, int>, pair<int, int>>> weights; // weight, best direction, min edges, second best min edges
    for (size_t i = 0; i < paths.size(); ++i) {
        if (i && get<0>(paths[i-1]) == get<0>(paths[i])) continue; // already considered
        pair<int, int> mn{INF, INF}; // min number of edges for this weight: edges, direction
        for (size_t j = i; j < paths.size() && get<0>(paths[j]) == get<0>(paths[i]); ++j) {
            mn = min(mn, {get<1>(paths[j]), get<2>(paths[j])});
        }
        int mn2 = INF; // min number of edges but in a different direction: edges
        for (size_t j = i; j < paths.size() && get<0>(paths[j]) == get<0>(paths[i]); ++j) {
            if (get<2>(paths[j]) != mn.second) mn2 = min(mn2, get<1>(paths[j]));
        }
        weights.push_back({{get<0>(paths[i]), mn.second}, {mn.first, mn2}});
    }

    int minEdges = INF;
    for (int i = 0, j = (int)weights.size()-1; i < (int)weights.size() && j >= 0; ++i) {
        while (j >= 0 && weights[i].first.first + weights[j].first.first > k) --j;
        if (j >= 0 && weights[i].first.first + weights[j].first.first == k) {
            int edges;
            if (weights[i].first.second == weights[j].first.second) {
                edges = min(weights[i].second.first + weights[j].second.second, weights[i].second.second + weights[j].second.first);
            } else edges = weights[i].second.first + weights[j].second.first;
            minEdges = min(minEdges, edges);
        }
    }
    for (size_t i = 0; i < weights.size(); ++i) {
        if (weights[i].first.first == k) minEdges = min(minEdges, weights[i].second.first);
    }

    // Recur on neighbor's components
    blockedNode[centroid] = true;
    for (auto [child, w] : g[centroid]) {
        if (!blockedNode[child]) minEdges = min(minEdges, getComponentMin(child, depth+1));
    }

    // Return minimum
    return minEdges;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    g.resize(n);
    blockedNode.resize(n);
    for (int i = 1; i < n; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    int minEdges = getComponentMin(0);
    cout << (minEdges == INF ? -1 : minEdges) << endl;
    return 0;
}