Codeforces Round #620 (Div. 2) E - 1-Trees and Queries

公式解説: Codeforces Round #620 (Div. 2) Editorial - Codeforces

問題概要

$n (3 \leq n \leq 10^5)$ 頂点の無向木が与えられる。次のクエリに $q (1 \leq n \leq 10^5)$ 回答えよ。

頂点 $x$ と頂点 $y$ の間に辺を追加する。このとき，頂点 $a$ と頂点 $b$ の間に $k (k \leq 10^9)$ 本の辺を通るパスは存在するか？

ただし，同じ辺を何度通ってもよく，辺の追加はクエリごとにリセットされる。

解法概要

追加した辺を使わないパスについてのみ考えてみる。

与えられるグラフは木なので，頂点 $a$，$b$ 間について最短路はただ1つ存在する。また，最短路以外の頂点 $a$，$b$ 間のパスについても，最短路から外れる→最短路に戻ってくるという手順によるパス長の伸ばし方しかできない。最短路から外れて戻ってくるときのパスは行きと帰りで同じになる。したがって，追加した辺を使わない場合は頂点 $a$，$b$ 間のパス長の偶奇を変えることはできない。よって，頂点 $a$，$b$ 間の最短路が $k$ 以下であり，かつ頂点 $a$，$b$ 間の最短路と $k$ の偶奇が一致する場合， YES が確定する。

YES が確定しない場合，追加した辺を使うパスについて考える必要がある。

追加した辺を使うパスの使い方は2種類に分けられる。

$a$ から $x$ に行き，追加した辺を通って $y$ に行き，　$y$ から $b$ に行く
$a$ から $y$ に行き，追加した辺を通って $x$ に行き，　$x$ から $b$ に行く

この2種類のパス長 $d$ について， $d \leq k$ でかつ $d$ と $k$ の偶奇が一致するという条件を満たすものがあれば YES が確定する。

ここまでで YES が確定しなければ NO である。

ソースコード

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

using namespace std;

constexpr int N_MAX = 100000;

vector<int> graph[N_MAX];

class LowestCommonAncestor {
    public:
    int root, n, LOG_V_MAX = 30;
    vector<int> depth;
    vector<vector<int>> parent;

    LowestCommonAncestor(int root=0, int n=N_MAX): root(root), n(n) {
        depth.assign(n, -1);
        parent.assign(n, vector<int>(LOG_V_MAX, -1));
        dfs(root, -1, 0);
        for(int j=1;j<LOG_V_MAX;++j) {
            for(int i=0;i<n;++i) {
                if(parent[i][j-1] == -1) continue;
                parent[i][j] = parent[parent[i][j-1]][j-1];
            }
        }
    }

    void dfs(int node, int par, int d) {
        depth[node] = d;
        parent[node][0] = par;
        for(auto child: graph[node]) {
            int c = child;
            if(c == par) continue;
            dfs(c, node, d+1);
        }
    }

    int get_lca(int u, int v) {
        if(depth[u] > depth[v]) swap(u, v);
        int depth_diff = depth[v] - depth[u];
        for(int j=0;j<LOG_V_MAX;++j) {
            if(depth_diff & (1 << j)) {
                v = parent[v][j];
            }
        }
        if(u == v) return u;
        for(int j=LOG_V_MAX-1;j>=0;--j) {
            if(parent[u][j] != parent[v][j]) {
                u = parent[u][j];
                v = parent[v][j];
            }
        }
        return parent[u][0];
    }
    
    int get_dist(int u, int v) {
        return depth[u] + depth[v] - 2*depth[get_lca(u, v)];
    }
};

void solve(LowestCommonAncestor &lca) {
    int x,y,a,b,k;
    cin >> x >> y >> a >> b >> k;
    --x; --y; --a; --b;
    int xy = lca.get_dist(x, y), ab = lca.get_dist(a, b);

    if(ab <= k && k % 2 == ab % 2) {
        cout << "YES\n";
        return;
    }
    int d = lca.get_dist(a, x) + 1 + lca.get_dist(y, b);
    if(d <= k && d % 2 == k % 2) {
        cout << "YES\n";
        return;
    }
    d = lca.get_dist(a, y) + 1 + lca.get_dist(x, b);
    if(d <= k && d % 2 == k % 2) {
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i=0;i<n-1;++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    LowestCommonAncestor lca = LowestCommonAncestor();

    int t;
    cin >> t;
    while(t--) {
        solve(lca);
    }
}

所感

サイクル長の偶奇が〜サイクルの中で $a$ と$b$ に最も近い頂点は〜とか言って泥沼にはまっていたけど，追加した辺を使うかどうかで分けて考察するとすっきりするね。