LCA,即在图论和计算机科学中，最近公共祖先（英語：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。　　——wikipedia

E. 1-Trees and Queries

Link: E. 1-Trees and Queries

Description

Gildong was hiking a mountain, walking by millions of trees. Inspired by them, he suddenly came up with an interesting idea for trees in data structures: What if we add another edge in a tree?

Then he found that such tree-like graphs are called 1-trees. Since Gildong was bored of solving too many tree problems, he wanted to see if similar techniques in trees can be used in 1-trees as well. Instead of solving it by himself, he's going to test you by providing queries on 1-trees.

First, he'll provide you a tree (not 1-tree) with n vertices, then he will ask you q queries. Each query contains 5 integers: x, y, a, b, and k. This means you're asked to determine if there exists a path from vertex a to b that contains exactly k edges after adding a bidirectional edge between vertices x and y. A path can contain the same vertices and same edges multiple times. All queries are independent of each other; i.e. the added edge in a query is removed in the next query.

Input
The first line contains an integer n (), the number of vertices of the tree.

Next n−1 lines contain two integers u and v () each, which means there is an edge between vertex u and v. All edges are bidirectional and distinct.

Next line contains an integer q (), the number of queries Gildong wants to ask.

Next q lines contain five integers x, y, a, b, and k each () – the integers explained in the description. It is guaranteed that the edge between x and y does not exist in the original tree.

Output
For each query, print "YES" if there exists a path that contains exactly k edges from vertex a to b after adding an edge between vertices x and y. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

Example

input
5
1 2
2 3
3 4
4 5
5
1 3 1 2 2
1 4 1 3 2
1 4 1 3 3
4 2 3 3 9
5 2 3 3 9
output
YES
YES
NO
YES
NO
Note
The image below describes the tree (circles and solid lines) and the added edges for each query (dotted lines).

Possible paths for the queries with "YES" answers are:

  • 1-st query: 1 – 3 – 2
  • 2-nd query: 1 – 2 – 3
  • 4-th query: 3 – 4 – 2 – 3 – 4 – 2 – 3 – 4 – 2 – 3

Problem solving

这道的意思就是给你一颗树，然后q次查询，每次查询输入五个数，x,y,a,b,k，问你x和y中间连接起来之后从a到b有没有路径长度为k的路。每次查询独立。如果有就输出“YES”，否则输出“NO”。并且本题中的路径可以经过一条边或一个点无数次。
所以我们可以发现，从a到b的最短距离是可以算出来的，我们只需要比较最短距离和k的奇偶性是否相同即可。因为假设这条最短路径为a,i,j,...,k,b，路径长度为x，走到b之后我们再从b走向k，然后再走向b。这样的话路径长度就变为了x+2i，i为任意正整数。所以只要x和k的奇偶性相同即可。当然，如果从a到b的最短距离已经大于k，那么肯定是不会有长度为k的路径的。
因此我们现在只需要考虑计算从a到b的最短距离。因为每次查询都会将一对xy连接起来。所以从a到b的最短路径有三种情况

  1. a->b
  2. a->x->y->b
  3. a->y->x->b

树上的两个点的最短距离可以用lca计算，树上两点ab的最短距离为dep[a]+dep[b]-dep[lca(a,b)]*2
所以我们可以据此求出上面列出来的三条路径的最短路长度跟k的奇偶性作比较，只要有一个满足奇偶性相同，就表明存在一条长度为k的路。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct node {
    int to, nxt;
} v[maxn << 1];
int head[maxn], cnt = 1, n, k, q, lg[maxn], dep[maxn], f[maxn][25];
void add(int from, int to)
{
    v[cnt].to = to;
    v[cnt].nxt = head[from];
    head[from] = cnt++;
}
void dfs(int x, int fa)
{
    f[x][0] = fa;
    dep[x] = dep[fa] + 1;
    for (int i = 1; i <= lg[dep[x]]; i++) f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = head[x]; i; i = v[i].nxt)
        if (v[i].to != fa) dfs(v[i].to, x);
}
int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) return x;
    for (int i = lg[dep[x]] - 1; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
int dis(int x, int y)
{
    return dep[x] + dep[y] - dep[lca(x, y)] * 2;
}
bool check(int x)
{
    if (x <= k && ((x & 1) == (k & 1))) return 1;
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        add(u, v); add(v, u);
    }
    for (int i = 1; i <= n; i++)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    dfs(1, 0);
    cin >> q;
    while (q--) {
        int a, b, x, y;
        cin >> x >> y >> a >> b >> k;
        if (check(dis(a, b)) || check(dis(a, x) + dis(y, b) + 1) || check(dis(a, y) + dis(x, b) + 1)) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

LCA模板

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
int n, m, s;
struct node {
    int to, next;
} v[maxn << 1];
int head[maxn], cnt = 1, dep[maxn], fa[maxn][30], lg[maxn];
void add(int from, int to)
{
    v[cnt].to = to;
    v[cnt].next = head[from];
    head[from] = cnt++;
}
void dfs(int x, int f)
{
    fa[x][0] = f; dep[x] = dep[f] + 1;
    for (int i = 1; i <= lg[dep[x]]; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int i = head[x]; i; i = v[i].next) if (v[i].to != f) dfs(v[i].to, x);
}
int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y])
        x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) return x;
    for (int i = lg[dep[x]] - 1; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m >> s;
    for (int x, y, i = 1; i <= n - 1; i++) {
        cin >> x >> y;
        add(x, y); add(y, x);
    }
    for (int i = 1; i <= n; i++) lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    dfs(s, 0);
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
}
赏