当前位置:网站首页>P4281 [ahoi2008] emergency assembly / gathering (LCA)
P4281 [ahoi2008] emergency assembly / gathering (LCA)
2022-07-05 00:05:00 【eva_ can(not)survive】
[AHOI2008] Emergency assembly / party - Luogu https://www.luogu.com.cn/problem/P4281 This question obviously needs to be used LCA Write , seek 3 One point, two liang LCA And then determine , If this 3 individual LCA Equal, then they meet at that point , If one is different , At that different meeting , It is impossible to have three different situations .
Correctness can be judged by drawing a picture .
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))
using P = pair<int, int>;
int n, m;
int head[MAXN];
int nxt[MAXN];
int ver[MAXN];
int cnt;
int dep[MAXN];
int LOG2[MAXN];
int fafa[MAXN][20];
void add(int x, int y) {
ver[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
void dfs(int p, int fa) {
fafa[p][0] = fa;
for (int i = 1; i <= LOG2[dep[p]]; i++) {
fafa[p][i] = fafa[fafa[p][i - 1]][i - 1];
}
for (int i = head[p]; i; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
dep[v] = dep[p] + 1;
dfs(v, p);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y])
swap(x, y);
while (dep[x] != dep[y]) {
x = fafa[x][LOG2[dep[x] - dep[y]]];
}
if (x == y)
return x;
for (int i = LOG2[dep[x]]; i >= 0; i--) {
if (fafa[x][i] != fafa[y][i])
x = fafa[x][i], y = fafa[y][i];
}
return fafa[x][0];
}
void solve() {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
int tmp1 = lca(x, y);
int tmp2 = lca(y, z);
int tmp3 = lca(x, z);
// printf("====%d %d %d\n", tmp1, tmp2, tmp3);
if (tmp1 == tmp2 && tmp1 == tmp3 && tmp2 == tmp3) {
printf("%d %d\n", tmp1, dep[x] + dep[y] + dep[z] - 3 * dep[tmp1]);
} else if (tmp1 == tmp2 && tmp1 != tmp3) {
printf("%d %d\n", tmp3, dep[x] + dep[z] - 2 * dep[tmp3] + dep[tmp3] + dep[y] - 2 * dep[tmp1]);
} else if (tmp1 == tmp3 && tmp1 != tmp2) {
printf("%d %d\n", tmp2, dep[y] + dep[z] - 2 * dep[tmp2] + dep[tmp2] + dep[x] - 2 * dep[tmp1]);
} else if (tmp2 == tmp3 && tmp1 != tmp2) {
printf("%d %d\n", tmp1, dep[x] + dep[y] - 2 * dep[tmp1] + dep[tmp1] + dep[z] - 2 * dep[tmp2]);
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 2; i <= n; i++) {
LOG2[i] = LOG2[i / 2] + 1;
}
dep[1] = 0;
int x, y;
for (int i = 1; i <= n - 1; i++) {
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
while (m--)
solve();
return 0;
}
边栏推荐
- P4281 [AHOI2008]紧急集合 / 聚会(LCA)
- Pytoch --- use pytoch to realize linknet for semantic segmentation
- Selected cutting-edge technical articles of Bi Ren Academy of science and technology
- 如何避免电弧产生?—— AAFD故障电弧探测器为您解决
- What is the difference between port mapping and port forwarding
- 如何有效对直流列头柜进行监测
- 圖解網絡:什麼是網關負載均衡協議GLBP?
- Application of fire fighting system based on 3D GIS platform
- How to apply for PMP project management certification examination?
- [IELTS reading] Wang Xiwei reading P4 (matching1)
猜你喜欢
How many triangles are there in the golden K-line diagram?
It's too convenient. You can complete the code release and approval by nailing it!
Tester's algorithm interview question - find mode
What is the difference between port mapping and port forwarding
Specification for fs4061a boost 8.4v charging IC chip and fs4061b boost 12.6V charging IC chip datasheet
电力运维云平台:开启电力系统“无人值班、少人值守”新模式
微服务(Microservice)那点事儿
Application of multi loop instrument in base station "switching to direct"
巩固表达式C# 案例简单变量运算
[paper reading] cavemix: a simple data augmentation method for brain vision segmentation
随机推荐
IT转测试岗,从迷茫到坚定我究竟付出了什么?
How to avoid arc generation—— Aafd fault arc detector solves the problem for you
企业公司项目开发好一部分基础功能,重要的事保存到线上第一a
海思3559万能平台搭建:YUV422的踩坑记录
If you open an account of Huatai Securities by stock speculation, is it safe to open an account online?
P4408 [NOI2003] 逃学的小孩(树的直径)
[论文阅读] TUN-Det: A Novel Network for Thyroid Ultrasound Nodule Detection
Paddleocr tutorial
Microservice
Best practice case of enterprise digital transformation: introduction and reference of cloud based digital platform system security measures
Actual combat simulation │ JWT login authentication
[论文阅读] CarveMix: A Simple Data Augmentation Method for Brain Lesion Segmentation
Acrel-EMS综合能效平台在校园建设的意义
认识ThreadPoolExecutor
uniapp上传头像
Meet ThreadPoolExecutor
A new method for analyzing the trend chart of London Silver
Jar batch management gadget
[kotlin] the third day
Is the account opening link of Huatai Securities with low commission safe?