题解 | 机房传信 #

$[模板+倍增]$

给你一棵树(因为n个节点，n-1条边)，每个节点的权值就是它的度数，然后若干次查询：求任意两个节点的最短路径上的权值之和

使用倍增的算法求解，我们知道 $dist(a,b)=depth[a]+ depth[b]-2\times depth[LCA(a,b)]$

使用相同的思想，在DFS中同时存储，从根节点到每个节点 $i$ 的权值之和，记为 $sum[i]$

那么是不是 $sum(a,b)=sum[a]+sum[b]-2\times sum[LCA(a,b)] ?$

但还是有问题，这里有一点需要警惕：

$dist(a,b)=depth[a]+ depth[b]-2\times depth[LCA(a,b)]$ ，这个公式是边的数量

而 $sum(a,b)=sum[a]+sum[b]-2\times sum[LCA(a,b)] ?$ 是求节点权值的和， $LCA(a,b)$ 这个点也在最短路径上，但是 $-2\times sum[LCA(a,b)]$ ，其中是把 $LCA(a,b)$ 这个点的权值给减掉了，所以还得加上，那么正确的公式应当为： $sum(a,b)=sum[a]+sum[b]-2\times sum[LCA(a,b)] + deg[LCA(a,b)]$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1e5 + 10;
const int M = 20;
int st[N][M];
int n, m;
int depth[N], deg[N], sum[N];
vector<int> adj[N];

void dfs(int u, int fa, int x, int dep){
    depth[u] = dep;
    sum[u] = x;
    st[u][0] = fa;
    for(int v : adj[u]){
        if(v != fa) dfs(v, u, x + deg[v], dep + 1);
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    int dif = depth[u] - depth[v];
    for(int i = M - 1; i >= 0; i --){
        if((dif >> i) & 1) u = st[u][i];
    }
    if(u == v) return u;
    for(int i = M  - 1; i >= 0; i --){
        if(st[u][i] != st[v][i]){
            u = st[u][i];
            v = st[v][i];
        }
    }
    return st[u][0];
}

signed main(){
    HelloWorld;
    
    cin >> n >> m;
    for(int i = 1; i <= n - 1; i ++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u] ++, deg[v] ++;
    }
    dfs(1, 1, deg[1], 1);
    for(int j = 1; j < M; j ++){
        for(int i = 1; i <= n; i ++) st[i][j] = st[st[i][j - 1]][j - 1];
    }
    while(m --){
        int u, v; cin >> u >> v;
        int lca1 = lca(u, v);
        cout << sum[u] + sum[v] - 2 * sum[lca1] + deg[lca1] << endl;
    }
    return 0;
}