NC50472. 聚会
描述
输入描述
第一行两个正整数，N和M。分别表示城市个数和聚会次数；
后面有N-1行，每行用两个正整数A和B表示编号为A和编号为B的城市之间有一条路。城市的编号是从1到N的；
再后面有M行，每行用三个正整数表示一次聚会的情况：小可可所在的城市编号，小卡卡所在的城市编号以及小YY所在的城市编号。
输出描述
一共有M行，每行两个数P和C，用一个空格隔开。表示第i次聚会的地点选择在编号为P的城市，总共的费用是经过C条道路所花费的费用。
示例1
输入:
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
C++ 解法, 执行用时: 1138ms, 内存消耗: 74488K, 提交时间: 2021-12-26 12:58:47
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 1;
int n,d[maxn],f[maxn][20];
vector <int> g[maxn];
void add(int &x,int &y){
g[x].push_back(y);
}
void init(int x){
d[x] = d[f[x][0]] + 1;
int len = g[x].size(),i;
for (i = 0;i < 19;i++)
f[x][i + 1] = f[f[x][i]][i];
for (i = 0;i < len;i++)
if (g[x][i] != f[x][0]){
f[g[x][i]][0] = x;
init(g[x][i]);
}
}
int lca(int x,int y){
if (d[x] < d[y])
swap(x,y);
int i;
for (i = 19;i >= 0;i--)
if (d[f[x][i]] >= d[y])
x = f[x][i];
if (x == y)return y;
for (i = 19;i >= 0;i--)
if (f[x][i] != f[y][i]){
x = f[x][i];
y = f[y][i];
}
return f[x][0];
}
int main(){
int m,x,y,z,t1,t2,t3,i;
scanf("%d%d",&n,&m);
for (i = 1;i < n;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
init(1);
while (m--){
scanf("%d%d%d",&x,&y,&z);
t1 = lca(x,y);
t2 = lca(x,z);
t3 = lca(y,z);
printf("%d %d\n",t1 ^ t2 ^ t3,d[x]+d[y]+d[z] - d[t1]-d[t2]-d[t3]);
}
return 0;
}