1 条题解

  • 1
    @ 2023-1-29 10:02:02
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 100000;
    const int MAXM = 100000;
    int n, q, root;          // 点数、询问个数、根节点
    vector<int> e[MAXN + 5]; // 存树
    int fa[MAXN + 5];
    int maxDep, dep[MAXN + 5];
    void dfs(int u, int father)
    {
        fa[u] = father;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (v == father)
                continue;
            dep[v] = dep[u] + 1;
            maxDep = max(maxDep, dep[v]);
            dfs(v, u);
        }
    }
    int lg2[MAXN + 5]; // 替代 log2(i)
    int dp[MAXN][35];  // i号点的 2^j 层祖先
    int lca(int u, int v)
    {
        if (dep[u] > dep[v])
            swap(u, v); // 让u的高度不低于v
        if (u == v)
            return u;
        // 把 v 提到与 u 同样高度
        for (int j = lg2[n]; j >= 0; j--)
            if ((1 << j) <= dep[v] - dep[u])
            {
                v = dp[v][j];
            }
        if (u == v)
            return u;
        // 找lca
        for (int j = lg2[n]; j >= 0; j--)
            if (dp[v][j] != dp[u][j])
            {
                v = dp[v][j],
                u = dp[u][j];
            }
        return dp[u][0];
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        //  输入
        cin >> n;
        root = 1;
        for (int i = 1; i <= n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        // 预处理:最大层数 maxDep、每个点的深度、记录父节点、log2[]、dp数组
        dep[root] = 0;
        maxDep = 1;
        dfs(root, 0);
        lg2[1] = 0;
        for (int i = 2; i <= n; i++)
            // i == 2^(log2(i-1)+1)
            if (i == (1 << (lg2[i - 1] + 1)))
                lg2[i] = lg2[i - 1] + 1;
            else
                lg2[i] = lg2[i - 1];
        for (int j = 0; j <= lg2[n]; j++)
        {
            for (int i = 1; i <= n; i++)
            {
                // 求解 dp[i][j]
                if (j == 0)
                    dp[i][j] = fa[i];
                else
                    dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        }
        // q 次询问
        cin >> q;
        while (q--)
        {
            int u, v;
            cin >> u >> v; // 求 lca(u,v)
            cout << dep[u] + dep[v] - 2 * dep[lca(u, v)] << "\n";
        }
        return 0;
    }
    
    
    • 1

    信息

    ID
    782
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    52
    已通过
    18
    上传者