仓鼠找 sugar
2022/5/25 23:22:40
本文主要是介绍仓鼠找 sugar,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
仓鼠找 sugar
LCA
SCUACM2022集训前训练-图论 - Virtual Judge (vjudge.net)
-
首先要观察出一个结论:若 a - b 的路径与 c - d 的路径相交,设 a, b 的 LCA 为 x; c, d 的 LCA 为 y
则有 x 在 c - d 路径上 或 y 在 a - b 路径上
-
如何判断一个点是否在一条路径上:
可观察到一个性质:若 x 在 a,b 路径上,则 \(dist(a,x) + dist(b,x) == dist(a,b)\)
-
求 \(dist(a,b)\): 设 \(t=lca(a,b)\), \(dist(a,b)=depth[a]-depth[t]+depth[b]-depth[t]\)
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long ll; const int N = 1e5 + 10, M = 21; int n, m, Q; int fa[N][M], depth[N]; vector<vector<int> > G(N); queue<int> q; void add(int a, int b) { G[a].push_back(b); } void bfs(int root) { q.push(root); memset(depth, 0x3f, sizeof depth); depth[0] = 0; depth[root] = 1; while(!q.empty()) { int t = q.front(); q.pop(); for (auto to : G[t]) { if (depth[to] != depth[t] - 1) { depth[to] = depth[t] + 1; fa[to][0] = t; q.push(to); for (int k = 1; k < M; k++) fa[to][k] = fa[fa[to][k-1]][k-1]; } } } } int lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); for (int k = M-1; k >= 0; k--) if (depth[fa[a][k]] >= depth[b]) a = fa[a][k]; if (a == b) return a; for (int k = M-1; k >= 0; k--) if (fa[a][k] != fa[b][k]) { a = fa[a][k]; b = fa[b][k]; } return fa[a][0]; } int dist(int a, int b) { int t = lca(a, b); return depth[a] + depth[b] - 2 * depth[t]; } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> Q; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; add(u, v), add(v, u); } bfs(1); while(Q--) { int a, b, c, d; cin >> a >> b >> c >> d; int x = lca(a, b), y = lca(c, d); if (dist(x, c) + dist(x, d) == dist(c, d) || dist(y, a) + dist(y, b) == dist(a, b)) cout << "Y" << endl; else cout << "N" << endl; } return 0; }
这篇关于仓鼠找 sugar的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?