题目大意：给你一棵树，和$3$个节点，要你找到树上的一个点，使得三个点到这个点的距离和最小，并输出个距离

题解：令三个点为$a,b,c$，$i,j$两点的$lca$为$lca_{i,j}$，第$i$个点的深度为$depth_i$，$i,j$两点之间的距离为$d_{i,j}$。所以会发现$lca_{a,b},lca_{b,c},lca_{a,c}$中至少有两个是相同的。

假设$lca_{a,b}==lca_{a,c}$：

$\therefore lca_{a,b,c}==lca_{a,b}==lca_{a,c}$

$$

\begin{align*}

ans&=d_{b,c}+d_{lca_{b,c},a}\\

&=d_{b,lca_{b,c}}+d_{lca_{b,c},c}+d_{lca_{b,c},lca_{a,b,c}}+d_{lca_{a,b,c},a}\\

&=depth_b+depth_c-2 \cdot depth_{lca_{b,c}}+depth_{lca_{b,c}}+depth_a-2\cdot depth_{lca_{a,b}}\\

&=depth_a+depth_b+depth_c+depth_{lca_{b,c}}-2\cdot depth_{lca_{a,b}}

\end{align*}

$$

再常规化：

$$

ans=depth_a+depth_b+depth_c+depth+\max\{depth_{lca_{a,b}},depth_{lca_{a,c}},depth_{lca_{b,c}}\}-2\cdot\min\{depth_{lca_{a,b}},depth_{lca_{a,c}},depth_{lca_{b,c}}\}

$$

卡点：倍增求$LCA$时$for$循环未循环到$1$

C++ Code：

#include 
     
      #define maxn 500010#define lb(x) (x & -x)using namespace std;int n, m;inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}int head[maxn], cnt;struct Edge {	int to, nxt;} e[maxn << 1];void addE(int a, int b) {	e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;}int dad[maxn][19], dep[maxn];void dfs(int rt) {	for (int i = head[rt]; i; i = e[i].nxt) {		int v = e[i].to;		if (v != dad[rt][0]) {			dep[v] = dep[rt] + 1;			dad[v][0] = rt;			dfs(v);		}	}}void init() {	for (int i = 1; i < 19; i++) {		for (int j = 1; j <= n; j++) {			dad[j][i] = dad[dad[j][i - 1]][i - 1];		}	}}int LCA(int x, int y) {	if (x == y) return x;	if (dep[x] < dep[y]) swap(x, y);	for (int t = dep[x] - dep[y]; t; t &= t - 1) x = dad[x][__builtin_ctz(lb(t))];	if (x == y) return x;	for (int i = 18; ~i; i--) if (dad[x][i] != dad[y][i]) x = dad[x][i], y = dad[y][i];	return dad[x][0];}int main() {	scanf("%d%d", &n, &m);	for (int i = 1; i < n; i++) {		int a, b;		scanf("%d%d", &a, &b);		addE(a, b);		addE(b, a);	}	dep[1] = 1;	dfs(1);	init();	while (m --> 0) {		int a, b, c, ans = 0;		scanf("%d%d%d", &a, &b, &c);		int lca_ab = LCA(a, b), lca_ac = LCA(a, c), lca_bc = LCA(b, c);		printf("%d ", lca_ab ^ lca_ac ^ lca_bc);		if (lca_ab == lca_ac) ans = dep[b] + dep[c] - dep[lca_bc] + dep[a] - (dep[lca_ac] << 1);		else {			if (lca_bc == lca_ab) ans = dep[a] + dep[c] - dep[lca_ac] + dep[b] - (dep[lca_ab] << 1);			else ans = dep[a] + dep[b] - dep[lca_ab] + dep[c] - (dep[lca_ac] << 1);		}		printf("%d\n", ans);			}	return 0;}