P8805 [蓝桥杯 2022 国 B] 机房

题目描述

这天，小明在机房学习。

他发现机房里一共有 $n$ 台电脑，编号为 $1$ 到 $n$，电脑和电脑之间有网线连接，一共有 $n-1$ 根网线将 $n$ 台电脑连接起来使得任意两台电脑都直接或者间接地相连。

小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和多少台电脑直接相连，而信息在网线中的传播时间可以忽略。比如如果某台电脑用网线直接连接了另外 $d$ 台电脑, 那么任何经过这台电脑的信息都会延迟 $d$ 单位时间 (发送方和接收方也会产生这样的延迟，当然如果发送方和接收方都是 同一台电脑就只会产生一次延迟)。

小明一共产生了 $m$ 个疑问：如果电脑 $u_{i}$ 向电脑 $v_{i}$ 发送信息，那么信息从 $u_{i}$ 传到 $v_{i}$ 的最短时间是多少?

输入格式

输入共 $n+m$ 行，第一行为两个正整数 $n, m$ 。

后面 $n-1$ 行，每行两个正整数 $x, y$ 表示编号为 $x$ 和 $y$ 的两台电脑用网线 直接相连。

后面 $m$ 行，每行两个正整数 $u_{i}, v_{i}$ 表示小明的第 $i$ 个疑问。

输出格式

输出共 $m$ 行，第 $i$ 行一个正整数表示小明第 $i$ 个疑问的答案。

输入输出样例 #1

输入 #1

4 3
1 2
1 3
2 4
2 3
3 4
3 3

输出 #1

5
6
1

说明/提示

【样例说明】

这四台电脑各自的延迟分别为 $2,2,1,1$ 。

对于第一个询问, 从 $2$ 到 $3$ 需要经过 $2,1,3$, 所以时间和为 $2+2+1=5$。对于第二个询问，从 $3$ 到 $4$ 需要经过 $3,1,2,4$，所以时间和为 $1+2+2+1=6$。

对于第三个询问，从 $3$ 到 $3$ 只会产生一次延迟, 所以时间为 1。

【评测用例规模与约定】

对于 $30 \%$ 的数据，保证 $n, m \leq 1000$;

对于 $100 \%$ 的数据，保证 $n, m \leq 10^5$。

蓝桥杯 2022 国赛 B 组 H 题。

很裸的一道lca的题目

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
const int M = 2e5 + 10;

int h[N], e[M], ne[M], idx;
int depth[N], fa[N][18];
int facility[N];
int sum_facility[N];
int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root)
{
    queue<int> q;
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0;
    depth[root] = 1;
    q.push(root);
    sum_facility[root] = facility[root];
    fa[root][0] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                sum_facility[j] = sum_facility[t] + facility[j];
                fa[j][0] = t;
                q.push(j);

                for (int k = 1; k <= 17; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);

    int diff = depth[a] - depth[b];
    for (int k = 0; k <= 17; k ++ )
        if (diff & (1 << k))
            a = fa[a][k];


    if (a == b) return a;

    for (int i = 17; i >= 0; i -- )
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }

    return fa[a][0];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
        facility[a] ++ , facility[b] ++ ;
    }

    bfs(1);

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

        LL res = sum_facility[a] + sum_facility[b];
        res = res - 2 * sum_facility[w] + facility[w];

        cout << res << endl;
    }

    return 0;
}