题目描述

给出一棵树$T$，一共$m$个询问，每次询问给出三个点$x,y,z$，在树上找到一个点$d$使得$\min(path(x,d)+path(y,d)+path(z,d))$。

思路

引理

有个显然的结论就是这个点只能在$LCA(x,y),LCA(x,z),LCA(y,z)$中的任意一个。

证明

对于任一种$d$在$LCA(u,v),(u,v\in\{x,y,z \},u\not=v)$的方案，如果将$d$放在$LCA$之外，其答案一定会变差。

在$LCA$

$$ ans=path(u,v)+path(k,LCA(u,v)) $$

不在$LCA$

$$ ans=path(u,v)+p+path(LCA(u,v),d)+path(k,d) $$

其中
$$ path(LCA(u,v),d)+path(k,d)\ge path(k,LCA(u,v)) $$
因此点$d$只能在$LCA(u,v),(u,v\in\{x,y,z \},u\not=v)$。

代码

#include <iostream>
#include <cstdio>

namespace wxy{
    const int N = 5e5 + 100;
    int head[N],fail[N << 1],edge[N << 1],tot;
    int n,m;
    int fa[N][50],d[N];
    bool vis[N];
    inline void add(int x,int y){
        edge[++tot] = y;
        fail[tot] = head[x];
        head[x] = tot;
    }
    void dfs(int u){
        vis[u] = true;
        for (int i = 1; (1 << i) <= n; i++)
            fa[u][i] = fa[fa[u][i-1]][i-1];
        for (int i = head[u];i;i = fail[i]){
            int v = edge[i];
            if (vis[v]) continue;
            d[v] = d[u] + 1;
            fa[v][0] = u;
            dfs(v);
        }
    }
    inline int lca(int x,int y){
        if (d[x] < d[y]) std::swap(x,y);
        int i,j;
        for (i = 0; (1 << i) <= n; i++);
        for (j = i;j >= 0; j--){
            if (d[fa[x][j]] >= d[y]){
                x = fa[x][j];
            }

        }

        if (x == y) return x;
        for (j = i;j >= 0; j--){
            if (fa[x][j] != fa[y][j]){
                x = fa[x][j];
                y = fa[y][j];
            }
        }
        return fa[x][0];
    }
    void main(){
        scanf("%d%d",&n,&m);
        tot = 0;
        for (int i = 1; i < n; i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        d[0] = -1;
        dfs(1);

        for (int i = 0; i < m; i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            int d1 = lca(x,y);
            int d2 = lca(x,z);
            int d3 = lca(y,z);
            int p1 = d[x]+d[y]+d[z]-2*d[lca(z,d1)]-d[d1];
            int p2 = d[x]+d[y]+d[z]-2*d[lca(y,d2)]-d[d2];
            int p3 = d[x]+d[y]+d[z]-2*d[lca(x,d3)]-d[d3];
            int ans = std::min(p1,std::min(p2,p3));
            if (ans == p1) printf("%d %d\n",d1,p1);
            else if (ans == p2) printf("%d %d\n",d2,p2);
            else if (ans == p3) printf("%d %d\n",d3,p3);
        }

    }
}signed main(){wxy::main();return 0;}