二话不说，直接按题意模拟暴搜，当然 \(O(nq)\) 的复杂度显然是寄了的。
不过，在模拟的过程中，我在链式前向星的删边中居然一开始错了，还是要 mark 一下以后注意。
void del(int x, int pre)
{
e[top].to = e[top].next = 0;
h[x] = pre; // h[x] = 0; < --- tip
}
int main()
{
int pre_x = h[x], pre_y = h[y];
del(x, pre_x);
del(y, pre_y);
}
这题主要是要想到在树上，从 \(x\to y\) 的简单路径与其余更长的路径的奇偶性是相同的 。
想到之后证明是显然的，所谓的更长路径其实就是在简单路径上多走了一些重复的边，一条边重复走一次来回就对答案有两次贡献，也就是 \(a = b + 2p~(p\in Z)\) ，显然， \(b\) 和 \(a\) 的奇偶性相同。
这样就有思路了，先分类讨论。
- 不走 \(x \longleftrightarrow y\)
也就是在原树上跑，显然与 \(k\) 的关系与树上两点距离有关，可以先用 lca + 树上前缀和求出简单路径的长度。
显然，如果 \(dis> k\) ，就一定不可能有路径满足 \(k\) 步可以到达，其他任意的路不管怎样都只会更大。
所以想到 若存在可行路径一定要保证 \(dis\leqslant k\) .
同时，因为 \(dis\) 不一定等于 \(k\) ，也就是说此时路径长度 \(k\) 要比 \(dis\) 大，
而若 \(dis\) 成立，则一定存在 \(dis + 2p\) ，那如果 \(k\in\{t|t = dis + 2p\}\)，则一定存在满足长度为 \(k\) 的路径。
也就是说，若存在可行路径，则 \(dis\) 和 \(k\) 的奇偶性一定相同 。
这样，\(dis \leqslant k\) 和 \(dis > k\) 就都讨论完了。
- 走 \(x \longleftrightarrow y\)
思路是一样的，同样求出 \(a\to b\) 且经过 \(x\to y\) 的简单路径。
而只加了一条边，贡献直接可以得到为 1，也就是求两边的 lca 即可：\(dis = dis_{a\to x} + 1 + dis_{y \to b}\) .
不过要注意的是，加的是无向边，所以要对于走一条边，要分成 \(x\to y\) 和 \(y\to x\) 两种不同的走法。
复杂度是 \(O(q\log n)\) .
#include <bits/stdc++.h>
#define re register int
using namespace std;
const int N = 1e5 + 10, logN = 50;
struct edge
{
int to, next;
}e[N];
int top, h[N], dep[N], st[N][logN], logn;
int n , q;
void add(int x, int y)
{
e[++ top] = (edge){y, h[x]};
h[x] = top;
}
void dfs(int x, int fa)
{
dep[x] = dep[fa] + 1;
st[x][0] = fa;
for (re i = 1; i <= logn; i ++)
st[x][i] = st[st[x][i - 1]][i - 1];
for (re i = h[x]; i; i = e[i].next)
{
int y = e[i].to;
if (y == fa) continue;
dfs(y, x);
}
}
int lca(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
for (re i = logn; ~ i; i --)
if (dep[st[x][i]] >= dep[y]) x = st[x][i];
if (x == y) return y;
for (re i = logn; ~ i; i --)
if (st[x][i] != st[y][i])
x = st[x][i], y = st[y][i];
return st[x][0];
}
int work(int x, int y)
{
int p = lca(x, y);
return dep[x] + dep[y] - (dep[p] << 1);
}
bool check(int x, int y)
{
return (x <= y && x % 2 == y % 2 ? true : false);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
logn = log2(n);
for (re i = 1; i < n; i ++)
{
int x, y;
cin >> x >> y;
add(x, y);
add(y, x);
}
dfs(1, 0);
cin >> q;
while (q --)
{
int x, y, a, b, k;
cin >> x >> y >> a >> b >> k;
int dis1 = work(x, y);
int dis2 = work(x, a) + 1 + work(b, y);
int dis3 = work(x, b) + 1 + work(a, y);
if (check(dis1, k) || check(dis2, k) || check(dis3, k))
cout << "YES\n";
else cout << "NO\n";
}
return 0;
}