This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t;
while (t--){
int n; cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++){
int u, v; cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
vector<bool> vis(n);
vector<int> dep(n);
vector<vector<int>> up(n, vector<int>(__lg(n) + 1));
function<void(int)> dfs = [&](int u){
vis[u] = 1;
for (auto &v: g[u]){
if (vis[v]) continue;
up[v][0] = u;
dep[v] = dep[u] + 1;
dfs(v);
}
vis[u] = 0;
};
dfs(0);
for (int j = 1; j <= __lg(n); j++){
for (int i = 0; i < n; i++){
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
auto lca = [&](int u, int v){
if (dep[u] < dep[v]) swap(u, v);
for (int i = __lg(n); i >= 0; i--){
if (dep[up[u][i]] >= dep[v]){
u = up[u][i];
}
}
if (u == v) return u;
for (int i = __lg(n); i >= 0; i--){
if (up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
};
vector<pair<int, int>> tag(n);
for (int i = 0; i < n; i++){
tag[i] = make_pair(i, i);
}
int q; cin >> q;
while (q--){
int u, v; cin >> u >> v;
u--, v--;
int l = lca(u, v);
if (dep[l] < dep[tag[u].first]){
tag[u].first = l;
}
if (dep[l] < dep[tag[v].second]){
tag[v].second = l;
}
}
bool flag = 0;
function<void(int)> solve = [&](int u){
vis[u] = 1;
pair<int, int> res{u, u};
for (auto &v: g[u]){
if (vis[v]) continue;
solve(v);
if (dep[tag[v].first] <= dep[u] && dep[tag[v].second] <= dep[u])
flag = 1;
if (dep[tag[v].first] <= dep[tag[u].first] || dep[tag[v].second] <= dep[tag[u].second])
flag = 1;
if (dep[tag[v].first] <= dep[res.first])
res.first = tag[v].first;
if (dep[tag[v].second] <= dep[res.second])
res.second = tag[v].second;
}
if (dep[res.first] <= dep[tag[u].first])
tag[u].first = res.first;
if (dep[res.second] <= dep[tag[u].second])
tag[u].second = res.second;
vis[u] = 0;
};
solve(0);
cout << (!flag? "Yes": "No") << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |