2742 聚会 (最近公共祖先LCA)
发布于 2021-09-02 12:56
题目描述
Y岛风景美丽宜人，气候温和，物产丰富。
Y岛上有N个城市（编号1,2,…,N），有N-1条城市间的道路连接着它们。
每一条道路都连接某两个城市。
幸运的是，小可可通过这些道路可以走遍Y岛的所有城市。
神奇的是，乘车经过每条道路所需要的费用都是一样的。
小可可，小卡卡和小YY经常想聚会，每次聚会，他们都会选择一个城市，使得3个人到达这个城市的总费用最小。
由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。
他们会提供给你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。
输入
第一行两个正整数，N和M，分别表示城市个数和聚会次数。N≤500000,M≤500000
后面有N-1行，每行用两个正整数A和B表示编号为A和编号为B的城市之间有一条路。
再后面有M行，每行用三个正整数表示一次聚会的情况：小可可所在的城市编号，小卡卡所在的城市编号以及小YY所在的城市编号。
输出
一共有M行，每行两个数Pos和Cost，用一个空格隔开，表示第i次聚会的地点选择在编号为Pos的城市，总共的费用是经过Cost条道路所花费的费用。
样例输入
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
样例输出
5 2
2 5
4 1
6 0
思路
先做树上的倍增，求出f[x][i]表示x的第2^i祖先。
对于询问a,b,c，聚会地点肯定是其中一个lca，将三种情况都尝试，距离最小的就是答案。
例如以pos=lca(a,b)，求a,b,c到pos的距离为dep[a]+dep[b]+dep[c]-dep[pos]-2*dep[lca(pos,c)];
需要吐槽的是，f[M][20]这样写不超时，f[20][M]这样写就超时...
using namespace std;const int M=500005;int n,m,pos,cost,ans1,ans2;int tot,head[M],Next[M*2],vet[M*2];int L,dep[M],f[M][20]; //写成f[20][M]就超时...void add(int a,int b){Next[++tot]=head[a],vet[tot]=b;head[a]=tot;}void dfs(int x,int pre){for(int i=head[x]; i; i=Next[i]){int y=vet[i]; if(y==pre) continue;f[y][0]=x; dep[y]=dep[x]+1;for(int j=1; j<L; j++) f[y][j]=f[f[y][j-1]][j-1];dfs(y,x);}}int lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=L-1; i>=0; i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=L-1; i>=0; i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];}int main(){scanf("%d%d",&n,&m);while((1<<L)<n) L++;for(int i=2; i<=n; i++){int a,b; scanf("%d%d",&a,&b);add(a,b); add(b,a);}dep[1]=1; dfs(1,0);for(int i=1; i<=m; i++){int a,b,c,t; scanf("%d%d%d",&a,&b,&c);pos=lca(a,b); t=lca(pos,c);cost=dep[a]+dep[b]+dep[c]-dep[pos]-2*dep[t];ans1=pos; ans2=cost;pos=lca(a,c); t=lca(pos,b);cost=dep[a]+dep[b]+dep[c]-dep[pos]-2*dep[t];if(cost<ans2){ans1=pos; ans2=cost;}cost=0;pos=lca(b,c); t=lca(pos,a);cost=dep[a]+dep[b]+dep[c]-dep[pos]-2*dep[t];if(cost<ans2){ans1=pos; ans2=cost;}printf("%d %d\n",ans1,ans2);}return 0;}
本文来自网络或网友投稿，如有侵犯您的权益，请发邮件至：aisoutu@outlook.com 我们将第一时间删除。
相关素材