思路：
显然那个集合点肯定是某两个点的LCA。
因为到LCA,两个点走的距离不会重叠。另外一点到LCA也没有重叠。
那么直接枚举LCA判断就行。
这里时间卡的很紧。
于是：链式向前星存图，倍增常数优化，卡卡常。
Code:
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 5e5+5; const int M = 1e6+5; const int Mod = 1e9+7; #define pi acos(-1) #define INF 1e8 #define INM INT_MIN #define rg register #define pb(a) push_back(a) #define mk(a,b) make_pair(a,b) #define dbg(x) cout << "now this num is " << x << endl; #define met0(axx) memset(axx,0,sizeof(axx)); #define metf(axx) memset(axx,-1,sizeof(axx)); #define sd(ax) scanf("%d",&ax) #define sld(ax) scanf("%lld",&ax) #define sldd(ax,bx) scanf("%lld %lld",&ax,&bx) #define sdd(ax,bx) scanf("%d %d",&ax,&bx) #define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx) #define sfd(ax) scanf("%lf",&ax) #define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx) #define pr(a) printf("%d\n",a) #define plr(a) printf("%lld\n",a) int f[N][25],lg[N],dep[N],cnt = 0,head[N]; struct Node{int to,next;}e[N<<1]; void add(int u,int v) { e[++cnt].to = v,e[cnt].next = head[u],head[u] = cnt; } inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void init() { for(int i=1;i<N;++i) lg[i] = lg[i-1]+(1<<lg[i-1] == i); } void dfs(int u,int fa) { dep[u] = dep[fa]+1,f[u][0] = fa; for(rg int i=1;i<=lg[dep[u]];++i) f[u][i] = f[f[u][i-1]][i-1]; for(rg int i = head[u];i;i=e[i].next) if(e[i].to != fa) dfs(e[i].to,u); } int LCA(int x,int y) { if(dep[x] < dep[y]) swap(x,y); while(dep[x] > dep[y]) x = f[x][lg[dep[x]-dep[y]]-1]; if(x == y) return x; for(rg int i = lg[dep[x]]-1;i >= 0;--i) { if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i]; } return f[x][0]; } int dis(int x,int y) { return dep[x]+dep[y]-2*dep[LCA(x,y)]; } void slove() { init(); int n,m; n = read(),m = read(); for(rg int i=1;i<n;++i) { int u,v; u = read(),v = read(); add(u,v);add(v,u); } dfs(1,0); for(rg int i=1;i<=m;++i) { int x,y,z; x = read(),y = read(),z = read(); int lca = LCA(x,y); int ans = dis(x,y)+dis(lca,z),pos = lca; lca = LCA(x,z); int tmp = dis(x,z)+dis(lca,y); if(tmp < ans) ans = tmp,pos = lca; lca = LCA(y,z); tmp = dis(y,z)+dis(lca,x); if(tmp < ans) ans = tmp,pos = lca; printf("%d %d\n",pos,ans); } } int main() { slove(); system("pause"); return 0; }