Editorial for Hoptiver

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

The connections form a tree on $n$ ~n~ nodes. The profit along the unique path between $a$ ~a~ and $b$ ~b~ is the sum of edge weights on that path.

Root the tree at node $0$ ~0~ and compute the distance $dist[v]$ ~dist[v]~ from the root to every node $v$ ~v~ (the sum of edge weights along that path). For any query $(a, b)$ ~(a, b)~:

$path(a, b) = dist[a] + dist[b] - 2 \cdot dist[\mathrm{lca}(a, b)]$ .

Compute LCAs with binary lifting in $O(\log n)$ ~O(\log n)~ per query after $O(n \log n)$ ~O(n \log n)~ preprocessing. Overall time is $O((n + q) \log n)$ ~O((n + q) \log n)~.

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int> > > adj;
vector<int> tin, tout, dist;
vector<vector<int> > up;
int timer_dfs = 0;
int LOGN;

void dfs(int v, int p, int d) {
    tin[v] = ++timer_dfs;
    dist[v] = d;
    up[v][0] = p;
    for (int i = 1; i < LOGN; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (size_t j = 0; j < adj[v].size(); j++) {
        int to = adj[v][j].first;
        int w = adj[v][j].second;
        if (to != p) {
            dfs(to, v, d + w);
        }
    }
    tout[v] = ++timer_dfs;
}

bool is_ancestor(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
    if (is_ancestor(a, b)) {
        return a;
    }
    if (is_ancestor(b, a)) {
        return b;
    }
    for (int i = LOGN - 1; i >= 0; i--) {
        if (!is_ancestor(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    adj.assign(n, vector<pair<int, int> >());
    tin.assign(n, 0);
    tout.assign(n, 0);
    dist.assign(n, 0);
    LOGN = 1;
    while ((1 << LOGN) <= n) {
        LOGN++;
    }
    up.assign(n, vector<int>(LOGN));

    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
    }

    dfs(0, 0, 0);

    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        int ancestor = lca(a, b);
        cout << dist[a] + dist[b] - 2 * dist[ancestor] << "\n";
    }
}

Comments

There are no comments at the moment.