CF - Duff in the Army

Official Analysis

Explanation

Note that for each two nodes $u$ and $v$, the path between them is just $u$ to $lca(u,v)$ and $v$ to $lca(u,v)$. Also note the constraint of $a \leq 10$ for each query. To answer each query, we only need to store the $10$ people with the smallest ids for the path from $u$ to $lca(u,v)$ and $v$ to $lca(u,v)$, and combine them. This can be done with binary lifting, which will store the $10$ smallest ids for each vertex to their $2^k$'th ancestor.

Implementation

We can answer each query in $\mathcal{O}(a \log n)$. Even though the constant factor is pretty bad, the problem limits give room for it. Note that if you do store more than $10$ smallest ids the problem will yield a MLE!

Time Complexity: $\mathcal{O}(a \log n)$ for each query.

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

const int MAXN = 1e5 + 1;
const int MAXL = 20;  // approximately maximum log
                      // for euler-tour
array<int, MAXN> enter_time, exit_time, depth;
int timer = 1;

// for binary lifting