男人女人做那事网站,网站开发 业务流程图,常州市建设工程管理中心网站,Wordpress判断来路 显示Problem - H - Codeforces
题意#xff1a; 思路#xff1a;
手玩一下样例就能发现简单结论#xff1a;
v 离它所在的树枝的根的距离 m 离这个根的距离时是 YES
否则就是NO
实现就很简单#xff0c;先去树上找环#xff0c;然后找出这个根#xff0c;分别给a 和…Problem - H - Codeforces
题意 思路
手玩一下样例就能发现简单结论
v 离它所在的树枝的根的距离 m 离这个根的距离时是 YES
否则就是NO
实现就很简单先去树上找环然后找出这个根分别给a 和 b BFS一遍得出两个dis数组比较一下即可
对于只有的环情况 和 m v 的情况需要特判
Code
#include bits/stdc.hconstexpr int N 2e5 10;
constexpr int M 1e6 10;
constexpr int Inf 1e9;std::queueint q1, q2;
std::vectorint 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;
}
