Problem - H - Codeforces
题意:
思路:
手玩一下样例就能发现简单结论:
v 离它所在的树枝的根的距离 < m 离这个根的距离时是 YES
否则就是NO
实现就很简单,先去树上找环,然后找出这个根,分别给a 和 b BFS一遍,得出两个dis数组,比较一下即可
对于只有的环情况 和 m = v 的情况需要特判
Code:文章来源:https://uudwc.com/A/edDNo
#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;
}
文章来源地址https://uudwc.com/A/edDNo