仓鼠找sugar
原题链接 仓鼠找sugar
题目大意
给你 n 个点， q 次询问，n−1 条边，每条边给出 u,v 两个点，代表 u,v 被一条边连接，接下来是q次询问，每次询问给你 x1,y1,x2,y2 让你判断 x1 到 y1 与 x2 到 y2 是否会经过相同的点
题目题解
跑LCA，然后判断
dist<x1, y1> + dist<x2, y2> >= dist<x1, x2> + dist<y1, y2>
dist<x, y> = depth[x] + depth[y] - 2 × depth[lca(x, y)]
第二个就是一个计算两点深度的，不多做解释，重点关注第一个不等式，以下证明正确性
分类证明：
对于一棵树而言 x1,y1 在根节点的左树里面， x2,y2 在根节点的右树里面 这样一定满足不等式对于一棵树而言 x1.y1,x2,y2 同时在根节点的左树（右树）里，那么此时又分情况 将其左树（右树）看成一棵以原根节点的下一个节点为根节点的树，此时分三种情况x1,y1 与 x2,y2 在不同边，此时满足我们第一点所说x1 或某一个点在左树，其他点在右树，将左侧的x1或其他点与右树应该加的点进行加法，然后再将右树的点用第一点所说处理即可，最终可以发现是满足我们的不等式x1,y2 同树，x2,y1 同树 参考第一点进行处理还有一种没有意义的情况就是再出现同在左树右树的情况 再以原树的根节点的下一点为根进行处理即可若就在原树中发生上述情况，也可按上述情况来进行处理，任何形态都是一样的详细看代码
#include <cstdio>
#include <cstring>
#include <iostream>
const int N = 100005;
int head[N << 1], to[N << 1], ver[N << 1];
int depth[N], f[N][22], lg[N];
bool Vis[N];
int tot;
void addedge(int x, int y) {
ver[tot] = y;
to[tot] = head[x];
head[x] = tot++;
}
void dfs(int x, int fa) {
depth[x] = depth[fa] + 1;
f[x][0] = fa;
for (int i = 1; (1 << i) <= depth[x]; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int i = head[x]; ~i; i = to[i]) {
int v = ver[i];
if(v != fa) {
Vis[v] = 1;
dfs(v, x);
}
}
}
int lca(int a, int b) {
if(depth[a] < depth[b]) {
std::swap(a, b);
}
while(depth[a] > depth[b]) {
a = f[a][lg[depth[a] - depth[b]] - 1];
}
if(a == b) return a;
for (int i = lg[depth[a]] - 1; i >= 0; i--) {
if(f[a][i] != f[b][i]) {
a = f[a][i];
b = f[b][i];
}
} return f[a][0];
}
int dist(int a, int b) {
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
int main() {
memset(head, -1, sizeof(head));
static int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
addedge(u, v);
addedge(v, u);
}
for (int i = 1; i <= n; i++) {
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}
for (int i = 1; i <= n; i++) {
if(!Vis[i]) {
Vis[i] = 1;
dfs(i, -1);
}
}
for (int i = 1; i <= m; i++) {
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
if(dist(x1, y1) + dist(x2, y2) >= dist(x1, x2) + dist(y1, y2)) puts("Y");
else puts("N");
} return 0;
}
cpp
运行
转载于:https://www.cnblogs.com/Nicoppa/p/11477981.html
