传送门 https://www.luogu.com.cn/problem/CF1304E
题目大意
给你一棵无根树, 然后询问 Q 次, 每次把点 $x$ 和点 $y$ 连接, 问你从点 $a$ 到点 $b$ 是否有一条长度为 $k$ 的简单路径, 每次询问完后会把新添加的边删除.
思路: 树上 LCA
题目跟 2019pjt4 很像, 可以说这个就是那道题的树上版本.
因为每次讯问完都会把新添的边删去, 所以我们只要想如何处理添完一条边后 $a$ 到 $b$ 的简单路径.
所以我们可以分两种情况讨论:
1. 把 $\left ( x,y \right )$ 算进 $\left ( a,b \right )$ 的路径.
2. 只算 $\left ( a,b \right )$ 的路径.
简单来说就是求 a->x-〉y->b 或 a->y->x->b 或 a->b 的路径, 众所周知树上两点之间的路径长度可以用 LCA 来求然后就没了.
但是怎么判断是否存在一条长度为 $k$ 的路径呢? 首先我们要知道:
如果我们向父亲节点走的话, 那么就会加两条边.
不理解的可以自己画一下图.
然后我们想一下, 如果 $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;
- }
来源: http://www.bubuko.com/infodetail-3422990.html