Code Festival Team Relay: B - Evergrowing Tree

solution

$O(Q \cdot (\log v_i + \log w_i))$。 毎回対数時間かけて合流するまで登っていけばよい。親を求めるのはいい感じにして$N$で割る。

$n = 1$の場合に注意。

implementation

#include <algorithm>
#include <cstdio>
using namespace std;
int main() {
    int n, q; scanf("%d%d", &n, &q);
    while (q --) {
        int i, j; scanf("%d%d", &i, &j); -- i; -- j;
        if (n == 1) {
            i = j = min(i, j);
        } else {
            while (i != j) {
                ((i > j ? i : j) -= 1) /= n;
            }
        }
        printf("%d\n", i + 1);
    }
    return 0;
}