由于题目补完才来写总结，导致前面的有的题目都需要重新再看一遍，只好当作复习了。
但考虑到趁热打铁，先看H.

H题：从小白视角来看乍一看是博弈论，仔细思考以后发现是图论。本题给的是基环树，意识到这一点很重要，这个条件是让本题不是很复杂的关键。n个点n条边且没有重边保证这个联通图中只有一个环。由于瓦能够预测马去哪，当双方在环上时，瓦永远不会被抓到。若开始时瓦不在环上，则瓦的最优策略是找到去环上的最短路，而马的策略尽可能先到环去拦截瓦。

梳理一下逻辑顺序，在环上找到离b最近的一点u，a如果能提前到u，则b就会被拦截。只需比较a到u的最短路和b到u的最短路大小就可以。

以上为算法思路，下面考虑用什么去实现上面这个思路？

首先dfs找到环，再bfs得到瓦到环上哪个点最近，确定u点后，再bfs找到a到u的最短距离。
bfs找最短路过程朴素，注意力放到dfs过程我学习到的点：
1.记录par父节点数组是为了能遍历环的时候找回去，找到环中距离b点最近的点。
2.对于只有一个环，利用dep深度数组去找，如果当前点x可拓展的点深度和dep[x]大小差2还能连在一起，则起码构成一个最小的三角环，建议自己画图理解dfs深度和环的关系。

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, a, b;
    std::cin >> n >> a >> b;
    a--, b--;
    
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    //在连通图中找到所有点离某个点的最短距离，返回的是一个vector
    //内部lambda函数的好处是可以不用预处理，随时执行，并可以将函数定义为变量
    auto bfs = [&](int s) {
        std::vector<int> dis(n, -1);
        dis[s] = 0;
        std::queue<int> q;
        q.push(s);
        
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            
            for (auto y : adj[x]) {
                if (dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    q.push(y);
                }
            }
        }
        return dis;
    };
    auto dis = bfs(b);
    
    int u = -1;
    std::vector<bool> vis(n);
    std::vector<int> par(n), dep(n);
    auto dfs = [&](auto self, int x) -> void {
        vis[x] = true;
        for (auto y : adj[x]) {
            if (!vis[y]) {
                par[y] = x;
                dep[y] = dep[x] + 1;
                self(self, y);
            } else if (dep[y] < dep[x] - 1) {//利用深度关系找到环
                for (int i = x; ; i = par[i]) {
                    if (u == -1 || dis[i] < dis[u]) {
                        u = i;//dijstra的模式找最短路，把第一次的情况u==-1的情况也考虑进去，可以一行特判我们应该固化下来
                    }//找到环中距离b点最近的点
                    if (i == y) {
                        break;
                        //环走完了，该及时退出循环
                    }
                }
            }
        }
    };
    dfs(dfs, 0);
    
    if (bfs(u)[a] > dis[u]) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

JZTXT

Codeforces Round 898 (Div. 4)

梳理一下逻辑顺序，在环上找到离b最近的一点u，a如果能提前到u，则b就会被拦截。只需比较a到u的最短路和b到u的最短路大小就可以。