CF-519E 題解

CF 519E.

題序

給一棵樹，對於每次詢問輸入 $a, b$，求有幾個點 $x$ 到 $a, b$ 的距離相同。

解法

• $x$ 有兩種情況： 1. $x$ 在 $a \rightarrow b$ 的路徑上：那麼 $x$ 介於 $a \rightarrow b$ 的路徑中點 $mid(a, b)$，也就是 $dis(a, x) = dis(x, b) = \frac{dis(a, b)}{2}$
  1. $x$ 不在 $a \rightarrow b$ 的路徑上：那麼一定存在一條道路使得 $x$ 能夠到達 $a \rightarrow b$ 的路徑中點 $mid(a, b)$
• 可以發現，不管是哪一種情況，都會跟路徑中點有關，且必須符合 $2 \mid dis(a, b)$ 才會有答案
• 要求出路徑中點，就需要先求出 $dis(a, b)$，這部分可以用 $LCA $ + 倍增法求出
• 有了 $dis(a, b)$ 之後，就可以利用求 LCA 的倍增表格，將 $a \text{ or } b$ 往上跳 $\frac{dis(a, b)}{2}$ 求出
• 至於求點數的部分，就是 $n - \displaystyle\sum_{i \in path(a, b)}{sizeof(subtree_i)}$：

Code

#define MAXN 200005
#define MAXM 1000005 
int n, m;
vector<int> G[MAXN];

struct Euler_Tour {
    int tt = 0;
    int in[MAXN], out[MAXN], d[MAXN], sz[MAXN];
    int arr[25][MAXN];

    bool isAnc(int i, int j) {
        return (in[i] <= in[j] && out[i] >= out[j]);
    }

    void init() {
        out[0] = INF;
    }

    void dfs(int i, int dep) {
        in[i] = ++tt;
        d[i] = dep;
        for (int e: G[i]) {
            if (!in[e]) {
                arr[0][e] = i;
                dfs(e, dep + 1);
                sz[i] += sz[e];
            }
        }
        out[i] = ++tt;
        sz[i]++;
    }

    void buildST() {        
        for (int i = 1; i <= __lg(n); i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = arr[i - 1][arr[i - 1][j]];
            }
        }
    }
} ET;

struct LCA {
    int find(int a, int b) {
        if (ET.in[a] > ET.in[b])
            swap(a, b);

        if (ET.isAnc(a, b)) {
            return a;
        }

        for (int i = 20; i >= 0; i--) {
            if (!ET.isAnc(ET.arr[i][a], b)) {
                a = ET.arr[i][a];
            }
        }

        return ET.arr[0][a];
    }

    int mv(int a, int dis) {
        for (int i = 20; i >= 0; i--) {
            if (dis >= (1 << i)) {
                a = ET.arr[i][a];
                dis -= (1 << i);
            }
        }
        return a;
    }
} LCA;

void sol() {
    cin >> n;
    for (int i = 1, a, b; i < n; i++) {
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }

    ET.init();
    ET.dfs(1, 1);
    ET.buildST();

    cin >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;

        if (a == b) {
            cout << n << endl;
            continue;
        }

        int lca = LCA.find(a, b);
        int disa = ET.d[a] - ET.d[lca];
        int disb = ET.d[b] - ET.d[lca];

        if ((disa + disb) % 2 == 0) {
            int mid = LCA.mv((disa > disb) ? a : b, (disa + disb) / 2);
            int ans = n;

            if (ET.isAnc(mid, a))
                ans -= ET.sz[LCA.mv(a, (disa + disb) / 2 - 1)];
            else
                ans -= n - ET.sz[mid];

            if (ET.isAnc(mid, b))
                ans -= ET.sz[LCA.mv(b, (disa + disb) / 2 - 1)];
            else
                ans -= n - ET.sz[mid];
                
            cout << ans << endl;
        }
        else {
            cout << 0 << endl;
        }
    }
}