Luogu p4281 [ahoi2008] emergency gathering / gathering solution

Luogu P4281 [AHOI2008] Emergency assembly / party Answer key

Topic link ：P4281 [AHOI2008] Emergency assembly / party

The question ： $m\le 5\times 10^5$ Time to ask , Ask one node at a time $t$ , Make three points on the tree $x,y,z$ （ Tree node number $n\le 5\times 10^5$ ） To $t$ The sum of the distances is the smallest , Output $t$ And the sum of distance

It's not hard to find out $x,y,z$ In pairs lca in

Different from the other two , Or the only difference is the answer

Why? ？ Because if you choose the same node ,

Suppose it is $(x,y),(x,z)$ Of LCA, be $t$ To $x$ The distance will be counted twice , $y$ To $z$ Will be counted once

If you choose a different one , be $y$ To $z$ Only once ,$t$ To $x$ Only once

So we can use difference to do

Here's a tip , The sum of distance is
$$d_x+d_y+d_z-d_{t_1}-d_{t_2}-d_{t_3}$$
The proof is simple , No more

Time complexity $O(m\log n)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
    
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
    
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){
    x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
    
        if(k<0){
    k=-k;pc('-');}
        static T stk[66];T top=0;
        do{
    stk[top++]=k%10,k/=10;}while(k);
        while(top){
    pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(5e5+15)

int n,Q,pos=1,lg[N],fa[N][20],head[N],dep[N];
struct Edge
{
    
    int u,v,next;
}e[N<<1];
void addEdge(int u,int v)
{
    
    e[++pos]={
    u,v,head[u]};
    head[u]=pos;
}
void dfs(int u,int f)
{
    
    fa[u][0]=f; dep[u]=dep[f]+1;
    for(int i=1; i<=lg[dep[u]]; i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u]; i; i=e[i].next)
        if(e[i].v!=f) dfs(e[i].v,u);
}
int lca(int x,int y)
{
    
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
    if(x==y) return x;
    for(int k=lg[dep[x]]-1; k>=0; k--)
    {
    
        if(fa[x][k]!=fa[y][k])
            x=fa[x][k],y=fa[y][k];
    }
    return fa[x][0];
}
signed main()
{
    
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(Q);
    for(int i=1,u,v; i<n; i++)
    {
    
        read(u);read(v);
        addEdge(u,v);addEdge(v,u);
    }
    for(int i=1; i<=n; i++)
        lg[i]=lg[i-1]+(1ll<<lg[i-1]==i);
    dfs(1,1);
    for(int x,y,z,t; Q--;)
    {
    
        read(x);read(y);read(z);
        int t1=lca(x,y), t2=lca(y,z), t3=lca(x,z);
        if(t1==t2)t=t3;if(t1==t3)t=t2;if(t2==t3)t=t1;
        int res=dep[x]+dep[y]+dep[z]-dep[t1]-dep[t2]-dep[t3];
        write(t);pc(' ');write(res);pc('\n');
    }
    return 0;
}