【简单图论】CF898 div4 H

Problem - H - Codeforces

题意：

思路：

手玩一下样例就能发现简单结论：

v 离它所在的树枝的根的距离 < m 离这个根的距离时是 YES

否则就是NO

实现就很简单，先去树上找环，然后找出这个根，分别给a 和 b BFS一遍，得出两个dis数组，比较一下即可

对于只有的环情况 和 m = v 的情况需要特判

Code：

#include <bits/stdc++.h>constexpr int N = 2e5 + 10;
constexpr int M = 1e6 + 10;
constexpr int Inf = 1e9;std::queue<int> q1, q2;
std::vector<int> adj[N];int n, a, b;
int top = 0;
int u[N], v[N];
int st[N], r[N];
int dis1[N];
int dis2[N];int find_r(int u, int fa) {if (st[u]) return u;st[u] = 1;for (auto v : adj[u]) {if (v == fa) continue;int t = find_r(v, u);if (t) {r[++ top] = u;st[u] = 2;return t == u ? 0 : t;}}return 0;
}
void bfs1(int u) {memset(dis1, 0x3f, sizeof(dis1));dis1[u]= 0;q1.push(u);while(!q1.empty()) {int u = q1.front();q1.pop();for (auto v : adj[u]) {if (dis1[v] > dis1[u] + 1) {dis1[v] = dis1[u] + 1;q1.push(v);}}}
}
void bfs2(int u) {memset(dis2, 0x3f, sizeof(dis2));dis2[u] = 0;q2.push(u);while(!q2.empty()) {int u = q2.front();q2.pop();for (auto v : adj[u]) {if (dis2[v] > dis2[u] + 1) {dis2[v] = dis2[u] + 1;q2.push(v);}}}
}
void solve() {std::cin >> n >> a >> b;top = 0;while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();for (int i = 1; i <= n; i ++) {st[i] = 0;adj[i].clear();}for (int i = 1; i <= n; i ++) {std::cin >> u[i] >> v[i];adj[u[i]].push_back(v[i]);adj[v[i]].push_back(u[i]);}if (a == b) {std::cout << "NO" << "\n";return;}find_r(1, 0);bfs1(b);int miu1 = Inf, ansu = 0;for (int i = 1; i <= n; i ++) {if (st[i] == 2 && miu1 > dis1[i]) {miu1 = dis1[i];ansu = i;}}if (st[b] == 2) {std::cout << "YES" << "\n";return;}bfs2(a);int ans1 = dis2[ansu];int ans2 = miu1;if (ans1 > ans2) std::cout << "YES" << "\n";else std::cout << "NO" << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while(t --) {solve();}return 0;
}