[AHOI2008]MEET 紧急集合

不会证明,只会观察.....

两点肯定到最好

三点求出两两的,然后....观察!!

发现三点的最短路就是用两条链把三点穿起来

所以距离是两两距离和除以二

然后三个最多有一个和其他的不同

那么就选那个相同的点作为集合点,这样只会有一个点需要多走

#include <iostream>
using namespace std;
const int maxn= 6e5+10; 
struct edge{
    int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v)
{
    d[++cnt] = (edge){v,head[u]},head[u] = cnt;
}
int fa[maxn][20],deep[maxn];
void dfs(int u,int faa)
{
    fa[u][0] = faa, deep[u] = deep[faa]+1;
    for(int i=1;i<=18;i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v==faa )    continue;
        dfs(v,u);
    }
}
int lca(int x,int y)
{
    if( deep[x]<deep[y] )    swap(x,y);
    for(int i=18;i>=0;i--)
        if( deep[fa[x][i]]>=deep[y] )    x=fa[x][i];
    if( x==y )    return x;
    for(int i=18;i>=0;i--)
        if( fa[x][i]!=fa[y][i] )
            x=fa[x][i],y = fa[y][i];
    return fa[x][0];
}
int dis(int x,int y)
{
    return deep[x]+deep[y]-2*deep[lca(x,y)];
}
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=1;i<n;i++)
    {
        int l,r; scanf("%d%d",&l,&r);
        add(l,r); add(r,l);
    }
    dfs(1,-1);
    for(int i=1;i<=m;i++)
    {
        int q,w,e,t; scanf("%d%d%d",&q,&w,&e);
        int t1 = lca(q,w),t2 = lca(q,e), t3 = lca(w,e);
        if( t1==t2 )    t = t3;
        else if( t1==t3 )    t = t2;
        else    t = t1;
        printf("%d %d\n",t,(dis(q,w)+dis(q,e)+dis(w,e))/2);
    }
}