BZOJ1832: [AHOI2008]聚会(LCA)
2019-08-26 05:38:51来源:博客园 阅读 ()
BZOJ1832: [AHOI2008]聚会(LCA)
题目:
1832: [AHOI2008]聚会
解析:
偶尔做做水题挺爽的
两两之间先求出LCA,发现至少有两个LCA是相同的,这个重复LCA也是深度最浅的那个,那我们就选择那个不重复的LCA,因为若选这个重复的LCA的话,这个重复的LCA到另一个LCA的路径会走两遍,反之只会走一遍
三点间的距离就是
\(dis[x] + dis[y] + dis[z] - dis[LCA(x, y)]- dis[LCA(x, z)]- dis[LCA(y, z)]\)
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, num;
int head[N], dep[N], f[N], size[N], top[N], son[N];
struct node {
int v, nx;
} e[N];
template<class T>inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
x = f ? -x : x;
return ;
}
inline void add(int u, int v) {
e[++num].nx = head[u], e[num].v = v, head[u] = num;
}
void dfs1(int u, int fa) {
size[u] = 1;
for (int i = head[u]; ~i; i = e[i].nx) {
int v = e[i].v;
if (v != fa) {
dep[v] = dep[u] + 1;
f[v] = u;
dfs1(v, u);
size[u] += size[v];
if (size[v] > size[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
if (son[u]) dfs2(son[u], t);
for (int i = head[u]; ~i; i = e[i].nx) {
int v = e[i].v;
if (v != f[u] && v != son[u]) dfs2(v, v);
}
}
int lca(int x, int y) {
int fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
x = f[fx], fx = top[x];
}
return dep[x] < dep[y] ? x : y;
}
int main() {
memset(head, -1, sizeof(head));
read(n), read(m);
for (int i = 1, x, y; i < n; ++i) read(x), read(y), add(x, y), add(y, x);
f[1] = 0, dep[1] = 1;
dfs1(1, 0);
dfs2(1, 1);
for (int i = 1, x, y, z; i <= m; ++i) {
read(x), read(y), read(z);
int a = lca(x, y), b = lca(x, z), c = lca(y, z);
int tmp = (dep[a] == dep[b]) ? c : ((dep[a] == dep[c]) ? b : a);
printf("%d %d\n", tmp, dep[x] + dep[y] + dep[z] - dep[a] - dep[b] - dep[c]);
}
}
原文链接:https://www.cnblogs.com/lykkk/p/11379217.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:有关同时进行两条线路的四维dp
下一篇:数位dp踩坑
- BZOJ3170: [Tjoi2013]松鼠聚会(切比雪夫距离转曼哈顿距离) 2018-07-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash