本文共 3444 字，大约阅读时间需要 11 分钟。

在背诵《诗经》的时候，小 G 回忆起了一棵树。树上有 5 个人，他们站在互不相同的节点上。

小 G 想去拜访他们，她会从某个人所在的节点出发，沿树上最短路径走向下一个人，以此类推，直到拜访完这 5 个人。 树上的所有边还未被翻新，翻新一条边需要一定的代价（边是双向的），而小 G 只愿意走被翻新过的边。她想知道，为了使得无论顺序如何都可以拜访完 5 个人，最小需要的翻新代价之和是多少。

输入格式

第一行，一个正整数 n，表示节点个数。

接下来 n-1 行，每行 3 个整数 u，v，w，表示 u 和 v 之间有一条边权为 w 的边。点的编号从 0 到 n-1，保证构成的是一棵树。 接下来一行，一个正整数 q，表示询问次数。 接下来 q 行，每行 5 个正整数 ，表示 5 个人所在的节点编号，保证它们互不相同。

输出格式

共 行，依次对应询问答案。

样例

input

5 0 1 1 1 2 2 2 3 3 3 4 4 1 4 0 3 1 2 output 10 input 6 4 0 4 0 1 2 1 3 9 3 5 1 3 2 5 2 4 0 3 5 2 0 4 1 3 5 output 21 16

题意

在一棵树上，找一棵包含5个节点的子树，求子树的大小。

通过最近公共祖先求解，前两个节点直接计算，并求出一个 pre_fa 表示前几个节点的共同祖先。后面每个节点进行判断，若新的祖先（now_fa）与 pre_fa 不同，则加上新旧两祖先间的距离，若相同则加上当前节点与前面节点中的最深祖先到该节点的距离。

实现代码

#include 
   
    using namespace std;#define ll long long#define MP make_pairusing namespace std;const int N = 1e6 + 100;const int M = 20;int n, m, q, dfs_cnt, st_cnt;int dfs_st[N * 2], ST_idx[N * 2], ST[N * 2][M + 1], rev[N * 2], Log[N * 2], lis[N * 2];ll dis[N], dep[N];vector
    
     
       > V[N];void dfs(int u, int fa) {    dfs_st[u] = ++dfs_cnt;    rev[dfs_cnt] = u;    ST[++st_cnt][0] = dfs_cnt;    lis[st_cnt] = dfs_cnt;    ST_idx[u] = st_cnt;    for (int i = 0; i < V[u].size(); i++) {        int v = V[u][i].first, c = V[u][i].second;        if (v == fa) continue;        dis[v] = dis[u] + c;        dep[v] = dep[u] + 1;        dfs(v, u);        ST[++st_cnt][0] = dfs_st[u];        lis[st_cnt] = dfs_st[u];    }}void init() {    for (int j = 1; j <= M; j++) {        for (int i = 1; i <= st_cnt; i++) {            ST[i][j] = min(ST[i][j - 1], ST[min(st_cnt, i + (1 << (j - 1)))]            [j - 1]);        }    }    int len = 1, cnt = 0;    for (int i = 1; i <= st_cnt; i++) {        if (len * 2 == i) {            len *= 2;            cnt++;        }        Log[i] = cnt;    }}// a b 的最近公共祖先int LCA(int a, int b) {    a = ST_idx[a], b = ST_idx[b];    if (a > b) {        swap(a, b);    }    int g = Log[b - a + 1];    return rev[min(ST[a][g], ST[b - (1 << g) + 1][g])];}// a 间 b 的距离ll DIS(int a, int b) {    int fa = LCA(a, b);    return dis[a] + dis[b] - 2 * dis[fa];}int main() {    int a, b, c;    scanf("%d", &n);    for (int i = 1; i < n; i++) {        scanf("%d%d%d", &a, &b, &c);        a++, b++;        V[a].push_back(MP(b, c));        V[b].push_back(MP(a, c));    }    dfs(1, 1);    init();    scanf("%d", &q);    for (int qq = 1; qq <= q; qq++) {        int a[6];        for (int i = 1; i <= 5; i++) {            scanf("%d", &a[i]);            a[i]++;        }        int ans = DIS(a[1], a[2]);//        cout << "add: " << ans << endl;        int pre_fa = LCA(a[1], a[2]);//        cout << "pre_fa: " << pre_fa << endl;        for (int i = 3; i <= 5; i++) {            int now_fa = LCA(pre_fa, a[i]);            if (now_fa != pre_fa) {                ans += DIS(pre_fa, a[i]);                pre_fa = now_fa;//                cout << "add: " << ans << endl;//                cout << "pre_fa: " << pre_fa << endl;            } else {                int max_depth_fa = now_fa;                for (int j = 1; j < i; j++) {                    int use = LCA(a[i], a[j]);                    if (dep[max_depth_fa] < dep[use]) {                        max_depth_fa = use;                    }                }                ans += dis[a[i]] - dis[max_depth_fa];//                cout << "add: " << dis[a[i]] - dis[max_depth_fa] << endl;//                cout << "pre_fa: " << pre_fa << endl;            }        }        printf("%d\n", ans);    }    return 0;}
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/113745865 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！