聚会

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1550 字

树上有三人各在一座城市，每次聚会选一城市P使

一本通
练习

正文

/*
原题：T1558 「一本通 4.4 练习 3」聚会 (AHOI 2008)
题意：树上有三人各在一座城市，每次聚会选一城市 P 使三人到 P 的总路程最小，输出 P 与总路程 C。
思路：三人 a,b,c 的聚会点即三个两两 LCA 中深度最大者；总路程 = (dist(a,b)+dist(b,c)+dist(c,a))/2。
复杂度：每次询问 O(log n)。
易错点：聚会点是“深度最大的两两 LCA”，不是简单求三者 LCA；总路程等于三对距离和的一半。
*/
#include <bits/stdc++.h>
using namespace std;
const int LOG=20;
int N,M;
vector<vector<int>> g;
vector<int> dep;
vector<vector<int>> up;
void dfs(int u,int p){
    up[u][0]=p;
    for(int i=1;i<LOG;i++) up[u][i]=up[up[u][i-1]][i-1];
    for(int v:g[u]){
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LOG-1;i>=0;i--)
        if(dep[x]-(1<<i)>=dep[y]) x=up[x][i];
    if(x==y) return x;
    for(int i=LOG-1;i>=0;i--)
        if(up[x][i]!=up[y][i]){ x=up[x][i]; y=up[y][i]; }
    return up[x][0];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N>>M;
    g.assign(N+1,vector<int>());
    for(int i=1;i<N;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dep.assign(N+1,0);
    up.assign(N+1,vector<int>(LOG,0));
    dfs(1,0);
    while(M--){
        int a,b,c;
        cin>>a>>b>>c;
        int ab=lca(a,b),bc=lca(b,c),ac=lca(a,c);
        int P;
        if(dep[ab]>=dep[bc]&&dep[ab]>=dep[ac]) P=ab;
        else if(dep[bc]>=dep[ab]&&dep[bc]>=dep[ac]) P=bc;
        else P=ac;
        int cost=(dep[a]+dep[b]-2*dep[ab]+dep[b]+dep[c]-2*dep[bc]+dep[a]+dep[c]-2*dep[ac])/2;
        cout<<P<<' '<<cost<<'\n';
    }
    return 0;
}

聚会

正文

一本通·提高篇的其它内容