题意：

在一颗 n 个节点的树上，有 q 个询问，每次询问给出x 、 y 、 z 三个节点，要求在树上找到一个点
$p$

p，使得
$distance = dist(x,p) + dist(y,p) + dist(z,p)$

distance=dist(x,p)+dist(y,p)+dist(z,p) 取得最小值;

思路:

最佳集合点
$p 只能是 LCA(x,y),LCA(y,z),LCA(x,z)$

p只能是LCA(x,y),LCA(y,z),LCA(x,z) 三者其中之一

$证明：$

证明：

当只有两个点
$x，y$

x，y 时，只要
$p$

p 在 x 到 y的路径上，
$dist(p,x)+dist(p,y)$

dist(p,x)+dist(p,y)，假设集合点一定在
$x$

x 到
$y$

y 的路径上。如今再加入
$z$

z 点，要做的是让
$dist(p,z)$

dist(p,z) 尽量小，设
$k = LCA(x,y)$

k=LCA(x,y) 。
当
$z$

z 不在
$k$

k 的子树下时，集合点应该选
$k$

k 即
$LCA(x,y)；$

LCA(x,y)；
当
$z$

z 在
$k$

k 的子树下时，分为两种情况：
①
$z$

z 在
$x$

x 或
$y$

y 的子树下，那么集合点就应该选
$x$

x 或
$y$

y 即
$LCA(x,z)和LCA(y,z)；$

LCA(x,z)和LCA(y,z)；
②
$z$

z 不在
$x$

x 的子树下且不在
$y$

y 的子树下时，集合点应该选
$k$

k 即
$LCA(x,y)；$

LCA(x,y)；
综上所述，
$p$

p 只可以取
$LCA(x,y)，LCA(y,z)，LCA(x,z)$

LCA(x,y)，LCA(y,z)，LCA(x,z)

再回到一开始，
$p$

p 点有没有可能不在
$x$

x 到
$y$

y 的路径上会使得
$distance$

distance 更小呢？
答案是不可能，画颗树可以知道：
如果
$z$

z 在
$x$

x 到
$y$

y 这条链上，集合点就在链的中间那个点上，这个点显然在链上
如果
$z$

z 不在这条链上，如果让集合点去靠近
$z$

z 目的来缩小
$dist(z,p)$

dist(z,p) ，
$x$

x 和
$y$

y 都会以两倍的奉还

因此我们可以知道最佳集合点
$p$

p 应该在
$x,y,z$

x,y,z 任意两点的路径上，即在路径
$x->y$

x−>y ，
$x->z$

x−>z ,
$y – > z$

y−>z，就是这三条路径的交点就是最佳集合点

另外这题用倍增似乎要开O₂ 和用快读才能过，而且听说会卡
$Tarjan$

Tarjan 有空补下树剖

#pragma GCC optimize(2) #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 5e5+10; int n,q,head[N],idx; pair<int,int> ans; struct Node{ int to,nex; }e[N<<1]; 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; } void add_edge(int u,int v){  e[idx].to = v;  e[idx].nex = head[u];  head[u] = idx++; } int dep[N],fa[N][20]; void dfs(int u,int f){  dep[u] = dep[f] + 1;  fa[u][0] = f; for(int i = head[u];~i;i = e[i].nex){ if(e[i].to != f){ dfs(e[i].to,u); } } } void init(){ for(int k = 1;(1<<k) <= n;k++){ for(int i = 1;i <= n;i++){    fa[i][k] = fa[fa[i][k-1]][k-1]; } } } int lca(int u,int v){ if(dep[u] < dep[v]) swap(u,v); if(dep[u] != dep[v]){ for(int i = 19;i >= 0;i--){ if(dep[fa[u][i]] >= dep[v]) u = fa[u][i]; } } if(u == v) return u; for(int i = 19;i >= 0;i--){ if(fa[u][i] != fa[v][i]){    u = fa[u][i],v = fa[v][i]; } } return fa[u][0]; } void cal(int x,int y,int z){ int lca1 = lca(x,y); int distance = dep[x]+dep[y]-2*dep[lca1]; int lca2 = lca(lca1,z);  distance += dep[lca1]+dep[z]-2*dep[lca2]; if(ans.second > distance){   ans.first = lca1;   ans.second = distance; } } int main(){  n = read();q = read(); //scanf("%d%d",&n,&q); memset(head,-1,sizeof(head)); for(int i = 1;i < n;i++){ int u,v;   u = read(),v = read(); //scanf("%d%d",&u,&v); add_edge(u,v);add_edge(v,u); } dfs(1,0); init(); while(q--){ int x,y,z;   x = read(),y = read(),z = read(); //scanf("%d%d%d",&x,&y,&z); int u = lca(x,y);   ans.first = -1,ans.second = inf; cal(x,y,z);cal(x,z,y);cal(y,z,x); printf("%d %dn",ans.first,ans.second); } return 0; }