「AHOI2008」紧急集合/聚会

题目描述

这次也是很长的题面啊(qwq)
题目大意如下：
给定一棵(N)个节点的树以及(M)次询问，每次询问给出(x, y, z)三个节点，程序需要在树上找一个点(p)
使得(c = dist(x,p)+dist(y,p)+dist(z,p))取最小值，每一次询问输出满足条件的(p)和此时的最小的(c)

基本思路

看到树上距离的题，很容易想到(LCA)，但是此处有三个点，不能直接用(LCA)，所以我们得绕一点弯...

考虑求出三个点两两之间的$LCA, $那么我们可以马上想到：

[p in { LCA(x,y),LCA(x,z),LCA(y,z)} ]

证明：

对于一条树上路径((x, y))，显然对于

[forall p in (x,y), dist(x,p)+dist(p,y)=dist(x,y) ]

所以该$ p (点并不会影响)x,y(的费用，所以我们应该尽可能使) p (点靠近) z $点

此时需要分类讨论：

(z in (x,y) ,)那么(p=z)
(z otin (x,y),)那么
1. (z in SubTree(x)()或 (z in SubTre(y)),p=x()或(p=y))
2. (z otin SubTree(x))且(z otin SubTree(y), z=LCA(x,y))

是不是感觉好麻烦？其实我们完全没必要做这么多。(qwq)
因为(x,y,z)是有轮换性的，所以只需要用某两个点之间的(LCA)试着更新(p)点就好了,结论也就是这么出来的
(具体过程可以根据上面的分类讨论，自己yy一下，最好画一张图~~我才不会告诉你我不会用几何画板~~)

细节注意事项

计算树上路径时，一定不要直接用(dep)去减，跑得过样例但是会WA

参考代码

#include <cstdio>
#include <cstring>
#define rg register
const int MAXN = 500010;
inline int abs(int a) { return a < 0 ? -a : a; }
inline void swap(int& a, int& b) { int t = a; a = b; b = t; }
inline int read() {
    int s = 0; bool f = false; char c = getchar();
    while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
    return f ? -s : s;
}
int tot, head[MAXN], nxt[MAXN << 1], ver[MAXN << 1];
inline void Add_edge(int u, int v) { nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }
int dep[MAXN], f[MAXN][22];
inline void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1, f[u][0] = fa;
    for (rg int i = 1; i <= 20; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for (rg int v, i = head[u]; i; i = nxt[i])
        if(!dep[v = ver[i]]) dfs(v, u);
}
inline int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (rg int i = 20; ~i; --i) if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (rg int i = 20; ~i; --i) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
int main() {
    int n = read(), q = read();
    for (rg int i = 1; i < n; i++) {
        int u = read(), v = read();
        Add_edge(u, v), Add_edge(v, u);
	}
    dfs(1, 0);
    for (rg int i = 1; i <= q; i++) {
        int x = read(), y = read(), z = read();
        int pos, minn = 2147483647, c;
        //根据轮换性(所以这三段都长得差不多...)
        int lca1 = LCA(x, y);
        c = dep[x] + dep[y] - 2 * dep[lca1];
        int lcaz = LCA(lca1, z);
        c += dep[lca1] + dep[z] - 2 * dep[lcaz];
        if (minn > c) pos = lca1, minn = c;
        
        int lca2 = LCA(x, z);
        c = dep[x] + dep[z] - 2 * dep[lca2];
        int lcay = LCA(lca2, y);
        c += dep[lca2] + dep[y] - 2 * dep[lcay];
        if (minn > c) pos = lca2, minn = c;
		
        int lca3 = LCA(y, z);
        c = dep[y] + dep[z] - 2 * dep[lca3];
        int lcax = LCA(lca3, x);
        c += dep[x] + dep[lca3] - 2 * dep[lcax];
        if (minn > c) pos = lca3, minn = c;
        
        printf("%d %d
", pos, minn);
    }
    return 0;
}

完结撒花(qwq)