当前位置:网站首页>P4281 [AHOI2008]紧急集合 / 聚会(LCA)
P4281 [AHOI2008]紧急集合 / 聚会(LCA)
2022-07-05 00:02:00 【eva_can(not)survive】
[AHOI2008]紧急集合 / 聚会 - 洛谷https://www.luogu.com.cn/problem/P4281这题很明显要用LCA写,求3个点两两LCA然后判断,如果这3个LCA相等那么他们就在该点汇合,若有一个不一样则,在那个不一样的汇合,不可能出现三个都不一样的情况。
正确性画个图就可以判断出来。
#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;
}
边栏推荐
- 45 year old professor, she threw two super unicorns
- 香港珠宝大亨,22亿“抄底”佐丹奴
- Tester's algorithm interview question - find mode
- 如何用快解析自制IoT云平台
- Every time I look at the interface documents of my colleagues, I get confused and have a lot of problems...
- Font design symbol combination multifunctional wechat applet source code
- How to do the project of computer remote company in foreign Internet?
- Pytoch --- use pytoch to realize linknet for semantic segmentation
- The input of uniapp is invalid except for numbers
- How to apply for PMP project management certification examination?
猜你喜欢
The input of uniapp is invalid except for numbers
[path planning] RRT adds dynamic model for trajectory planning
How to apply for PMP project management certification examination?
高配笔记本使用CAD搬砖时卡死解决记录
Fast parsing intranet penetration helps enterprises quickly achieve collaborative office
[kotlin] the third day
Application of multi loop instrument in base station "switching to direct"
Hong Kong Jewelry tycoon, 2.2 billion "bargain hunting" Giordano
Some basic functions of enterprise projects are developed, and important things are saved to online first a
45 year old professor, she threw two super unicorns
随机推荐
Paddleocr tutorial
Go step on the pit - no required module provides package: go mod file not found in current directory or any parent
【雅思阅读】王希伟阅读P4(matching1)
微服务(Microservice)那点事儿
巩固表达式C# 案例简单变量运算
Enterprise application business scenarios, function addition and modification of C source code
[论文阅读] CarveMix: A Simple Data Augmentation Method for Brain Lesion Segmentation
如何避免电弧产生?—— AAFD故障电弧探测器为您解决
In June, the list of winners of "Moli original author program" was announced! Invite you to talk about the domestic database
如何在外地外网电脑远程公司项目?
Why does infographic help your SEO
go踩坑——no required module provides package : go.mod file not found in current directory or any parent
Intelligence test to see idioms guess ancient poems wechat applet source code
uniapp 除了数字,其他输入无效
Fast parsing intranet penetration helps enterprises quickly achieve collaborative office
go踩坑——no required module provides package : go.mod file not found in current directory or any parent
【北京大学】Tensorflow2.0-1-开篇
JS how to realize array to tree
微软禁用IE浏览器后,打开IE浏览器闪退解决办法
业务实现-日志写到同一个行数据里面