欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ1832: [AHOI2008]聚会(LCA)

程序员文章站 2022-06-21 22:40:10
题目: "1832: [AHOI2008]聚会" 解析: 偶尔做做水题挺爽的 两两之间先求出LCA,发现至少有两个LCA是相同的,这个重复LCA也是深度最浅的那个,那我们就选择那个不重复的LCA,因为若选这个重复的LCA的话,这个重复的LCA到另一个LCA的路径会走两遍,反之只会走一遍 三点间的距离 ......

题目:

1832: [ahoi2008]聚会

解析:

偶尔做做水题挺爽的
两两之间先求出lca,发现至少有两个lca是相同的,这个重复lca也是深度最浅的那个,那我们就选择那个不重复的lca,因为若选这个重复的lca的话,这个重复的lca到另一个lca的路径会走两遍,反之只会走一遍
三点间的距离就是
\(dis[x] + dis[y] + dis[z] - dis[lca(x, y)]- dis[lca(x, z)]- dis[lca(y, z)]\)

代码:

#include <bits/stdc++.h>
using namespace std;
const int n = 1e6 + 10;
int n, m, num;
int head[n], dep[n], f[n], size[n], top[n], son[n];
struct node {
    int v, nx;
} e[n];

template<class t>inline void read(t &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u, int v) {
    e[++num].nx = head[u], e[num].v = v, head[u] = num;
}

void dfs1(int u, int fa) {
    size[u] = 1;
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (v != fa) {
            dep[v] = dep[u] + 1;
            f[v] = u;
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > size[son[u]]) son[u] = v;
        }
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (v != f[u] && v != son[u]) dfs2(v, v);
    }
}

int lca(int x, int y) {
    int fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
        x = f[fx], fx = top[x];
    }
    return dep[x] < dep[y] ? x : y;
}

int main() {
    memset(head, -1, sizeof(head));
    read(n), read(m);
    for (int i = 1, x, y; i < n; ++i) read(x), read(y), add(x, y), add(y, x);
    f[1] = 0, dep[1] = 1;
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1, x, y, z; i <= m; ++i) {
        read(x), read(y), read(z);
        int a = lca(x, y), b = lca(x, z), c = lca(y, z);
        int tmp = (dep[a] == dep[b]) ? c : ((dep[a] == dep[c]) ? b : a);
        printf("%d %d\n", tmp, dep[x] + dep[y] + dep[z] - dep[a] - dep[b] - dep[c]);
    }
}