题解

CF620D2E

由于一条路径可以包含一条边多次，所以如果$a$能经历$k$条边到达$b$，那就可以经过$k+2n$条边到达$b$，只需要在路径中随便找一条边不停折返即可。于是考虑对树黑白染色，（注意结论，即树是二分图，从而可以dfs染成黑白两色，方便考虑）。

那么从每个结点出发，用奇数步可以到达所有异色的结点，用偶数步可以到达所有同色的结点（这里是指，只要步数取遍所有奇数，就可以到达所有异色的结点，偶数同理）。从而对每次询问，只需判断$a,b$是否同色，就能知道$a,b$之间的任意一条路径长度是奇数还是偶数。然后直接与$k$比较即可得知有没有可能花$k$步到达。如果要算上$x,y$的影响，不难想到当且仅当$x,y$同色时才会对奇偶性产生影响。当$x,y$同色时，从任意节点出发，可以用奇数步到达任意节点，也可以用偶数步到达任意节点。

但是，这题必须要考虑$k$是否大于$a,b$间的最短距离。要求得$a,b$间的最短距离$d(a,b)$，不难想到$a$应当先行进到它们的最近公共祖先（Least Common Ancestors, LCA）$LCA(a,b)$，再行进到$b$。即使没有接触过求最近公共祖先的算法，也应当能够想到这一步。这样显然有$d(a,b)=(deep[a]-deep[LCA(a,b)]) + (deep[b] - deep[LCA(a,b)])$。然后可以使用各种求最近公共祖先的算法，应该都可以过。我使用的是tarjan算法。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#define maxn 100005
using namespace std;
void tarjan(int u);
void merge(int u, int v);
int find(int u);
void add_query(int x, int y, int num);
struct query {
    int to, num;
    query(int _to, int _num) {
        this->to = _to;
        this->num = _num;
    }
    //num: index in Q[]
};
vector<query> Gq[maxn];//每个顶点的请求列表 
vector<int> G[maxn];//原图 
int Q[5 * maxn];
//Q[5 * i]: ab[i]
//Q[5 * i + 1]: xa[i]
//Q[5 * i + 2]: yb[i]
//Q[5 * i + 3]: xb[i]
//Q[5 * i + 4]: ya[i]
int deep[maxn];
int k[maxn];
int fa[maxn];
bool vis[maxn];
int main() {
    cin.tie(0);
    cout.tie(0);
    cin.sync_with_stdio(0);
    int n, u, v;
    cin >> n;
    for(int i = 1; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        fa[i] = i;
    }
    fa[n] = n;
    int q, x, y, a, b;
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> x >> y >> a >> b >> (k[i]);
        add_query(a, b, 5 * i);
        add_query(x, a, 5 * i + 1);
        add_query(y, b, 5 * i + 2);
        add_query(x, b, 5 * i + 3);
        add_query(y, a, 5 * i + 4);
    }
    tarjan(1);
    bool ok;
    for(int i = 0; i < q; i++) {
        ok = false;
        int ab = Q[5 * i], xa = Q[5 * i + 1], yb = Q[5 * i + 2], xb = Q[5 * i + 3], ya = Q[5 * i + 4];
        if(((k[i] + ab) & 1) == 0 && k[i] >= ab) {
            ok = true;
        } else if(((k[i] + xa + yb + 1) & 1) == 0 && k[i] >= xa + yb + 1) {
            ok = true;
        } else if(((k[i] + xb + ya + 1) & 1) == 0 && k[i] >= xb + ya + 1) {
            ok = true;
        }
        cout << (ok ? "YES" : "NO") << endl;
    }
    return 0;
}
void tarjan(int u) {
    vis[u] = true;
    for(int i = 0; i < G[u].size(); i++) {
        if(vis[G[u][i]]) continue;
        deep[G[u][i]] = deep[u] + 1;
        tarjan(G[u][i]);
        merge(G[u][i], u);
        //注意u和G[u][i]的顺序， 参见函数实现处注释 
    }
    for(int i = 0; i < Gq[u].size(); i++) {
        if(!vis[Gq[u][i].to]) continue;
        Q[Gq[u][i].num] = deep[u] + deep[Gq[u][i].to] - 2 * deep[ find(Gq[u][i].to) ];
    }
}

void add_query(int x, int y, int num) {
    Gq[x].push_back(query(y, num));
    Gq[y].push_back(query(x, num));
}
//并查集 
void merge(int u, int v) {
    fa[find(u)] = find(v);
    //注意：一定要把深度小的结点并到深度大的节点下，否则会出错 
    //我这里是在调用的时候保证了这一点，也可以选择在实现的时候判断一下 
}
int find(int u) {
    return (fa[u] == u ? u : fa[u] = find(fa[u]));
}