cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2014 · MediumLowest common ancestor

Fuel on Tree Routes

National Olympiad — National round

Submission name: fuel.cpp

Solve in Editor →

Problem summary

N cities form a weighted undirected tree. Each unit of road length consumes one unit of fuel. For each query, report the fuel needed on the unique route between the two named cities.

Input

N Q; N−1 triples u v w; Q vertex pairs.

Output

One route length per query in input order.

Constraints

1≤N≤5000; 1≤Q≤200000; 1≤w≤2000000; memory limit 16 MB. Half the tests have N≤2000,Q≤10000.

Worked example

An independently prepared example for this explanation.

Input

4 3
1 2 4
2 3 7
2 4 2
3 4
1 3
2 2

Output

9
11
0

Solution analysis

  1. Root the tree at 1 and calculate depth and weighted root distance iteratively.
  2. Build binary-lifting ancestors to answer lowest-common-ancestor queries.
  3. For L=LCA(u,v), return dist[u]+dist[v]−2·dist[L].

Why it works

The two root routes share exactly the route from root to L. Subtracting its length twice leaves precisely the unique u–v path. Binary lifting raises vertices without skipping their lowest common ancestor.

Complexity: O((N+Q) log N) time and O(N log N) space, within 16 MB.

Watch out. Weighted distances require 64-bit integers; avoid an N² distance matrix.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: The two root routes share exactly the route from root to L. Subtracting its length twice
// leaves precisely the unique u–v path.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<vector<pair<int,int>>>g(n+1);
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    int L=1;
    while((1<<L)<=n){
        L++;
    }
    vector<vector<int>>up(L,vector<int>(n+1));
    vector<int>dep(n+1),order{1};
    vector<long long>d(n+1);
    for(size_t i=0;i<order.size();i++){
        int u=order[i];
        for(auto[v,w]:g[u]){
            if(v!=up[0][u]){
                up[0][v]=u;
                dep[v]=dep[u]+1;
                d[v]=d[u]+w;
                order.push_back(v);
            }
        }
    }
    for(int k=1;k<L;k++){
        for(int v=1;v<=n;v++){
            up[k][v]=up[k-1][up[k-1][v]];
        }
    }
    auto lca=[&](int a,int b){
        if(dep[a]<dep[b]){
            swap(a,b);
        }
        int diff=dep[a]-dep[b];
        for(int k=0;k<L;k++){
            if(diff>>k&1){
                a=up[k][a];
            }
        }
        if(a==b){
            return a;
        }
        for(int k=L-1;k>=0;k--){
            if(up[k][a]!=up[k][b]){
                a=up[k][a];
                b=up[k][b];
            }
        }
        return up[0][a];
    };
    while(q--){
        int a,b;
        cin>>a>>b;
        cout<<d[a]+d[b]-2*d[lca(a,b)]<<'\n';
    }
}

Source: Arena Olimpiici ↗