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代码

#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]的顺序<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span> 参见函数实现处注释 
    }
    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);
    //注意<span class="bd-box"><h-char class="bd bd-beg"><h-inner>:</h-inner></h-char></span>一定要把深度小的结点并到深度大的节点下<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>否则会出错 
    //我这里是在调用的时候保证了这一点<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>也可以选择在实现的时候判断一下 
}
int find(int u) {
    return (fa[u] == u ? u : fa[u] = find(fa[u]));
}