题目大意
给你一棵无根树,然后询问 $Q$ 次,每次把点 $x$ 和点 $y$ 连接,问你从点 $a$ 到点 $b$ 是否有一条长度为 $k$ 的简单路径,每次询问完后会把新添加的边删除。
思路:树上LCA
题目跟 2019pjt4 很像,可以说这个就是那道题的树上版本。
因为每次讯问完都会把新添的边删去,所以我们只要想如何处理添完一条边后 $a$ 到 $b$ 的简单路径。
所以我们可以分两种情况讨论:
- 把 $left ( x,y ight )$ 算进 $left ( a,b ight )$ 的路径。
- 只算 $left ( a,b ight )$ 的路径。
简单来说就是求 $a->x->y->b$ 或 $a->y->x->b$ 或 $a->b$ 的路径,树上两点之间的路径长度可以用 LCA 求出。
然后我们想一下,如果 $k$ 比路径长度大的话,我们就往父亲节点走,很容易发现,如果多出来的部分如果不是 $2$ 的倍数的话,那么就不存在一条长度为 $k$ 的路径。
不理解的可以自己画一下图。
代码
#include <bits/stdc++.h>
#define RI register int
using namespace std;
template <class T>
inline void read(T &x) {
T f = 1; x = 0; char c = getchar();
while(c > '9' || c < '0') {
if(c == '-')
f = -f;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
x *= f;
}
const int N = 1e5 + 7;
int n;
struct Edge {
int nxt, to;
} edge[N << 1];
int head[N], tot;
int dep[N], st[N][21];
inline void add(int x, int y) {
edge[++tot].nxt = head[x];
edge[tot].to = y;
head[x] = tot;
}
inline void Read() {
read(n);
for(RI i = 1; i < n; i++) {
int x, y;
read(x), read(y);
add(x, y);
add(y, x);
}
}
inline void dfs(int x, int fa) {
dep[x] = dep[fa] + 1;
st[x][0] = fa;
for(RI i = 1; i <= 20; i++)
st[x][i] = st[st[x][i - 1]][i - 1];
for(RI i = head[x]; i; i = edge[i].nxt) {
int y = edge[i].to;
if(y == fa)
continue;
dfs(y, x);
}
}
inline int Lca(int x, int y) {
if(dep[y] > dep[x])
swap(x, y);
for(RI i = 20; i >= 0; i--)
if(dep[st[x][i]] >= dep[y])
x = st[x][i];
if(x == y)
return x;
for(RI i = 20; i >= 0; i--)
if(st[x][i] != st[y][i])
x = st[x][i], y = st[y][i];
return st[x][0];
}
int main() {
Read();
dfs(1, 0);
int T;
read(T);
while(T--) {
int x, y, a, b, k;
int res1, res2, res3;
read(x), read(y), read(a), read(b), read(k);
int Lca1 = Lca(a, b), Lca2_1 = Lca(a,x), Lca2_2 = Lca(y,b), Lca3_1 = Lca(a,y), Lca3_2 = Lca(x,b);
res1 = dep[a] + dep[b] - 2 * dep[Lca1];
res2 = dep[a] + dep[x] + dep[y] + dep[b] - 2 * dep[Lca2_1] - 2 * dep[Lca2_2] + 1;
res3 = dep[a] + dep[x] + dep[y] + dep[b] - 2 * dep[Lca3_1] - 2 * dep[Lca3_2] + 1;
if(res1 <= k && (k - res1) % 2 == 0) {
puts("YES");
continue;
}
if(res2 <= k && (k - res2) % 2 == 0) {
puts("YES");
continue;
}
if(res3 <= k && (k - res3) % 2 == 0) {
puts("YES");
continue;
}
puts("NO");
}
return 0;
}