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 <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
struct FT{
vector<int> bit;
int n;
FT(int ns){
n = ns;
bit.resize(n + 1);
}
void add(int v, int k){
while (v <= n){
bit[v] += k;
v |= (v + 1);
}
}
void upd(int l, int r, int x){
add(l, x);
add(r + 1, -x);
}
int get(int v){
int out = 0;
while (v > 0){
out += bit[v];
v = (v & (v + 1)) - 1;
}
return out;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt; cin>>tt;
while (tt--){
int n; cin>>n;
vector<int> g[n + 1];
for (int i = 1; i < n; i++){
int a, b; cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
const int lg = log2(n);
vector<vector<int>> pw(n + 1, vector<int>(lg + 1));
vector<int> tin(n + 1), tout(n + 1);
int timer = 0;
function<void(int, int)> fill = [&](int v, int pr){
tin[v] = ++timer;
pw[v][0] = pr;
for (int i = 1; i <= lg; i++){
pw[v][i] = pw[pw[v][i - 1]][i - 1];
}
for (int i: g[v]){
if (i == pr) continue;
fill(i, v);
}
tout[v] = timer;
};
fill(1, 1);
auto check = [&](int x, int y){
return (tin[x] <= tin[y] && tout[x] >= tout[y]);
};
int m; cin>>m;
vector<int> s(m + 1), t(m + 1);
for (int i = 1; i <= m; i++){
cin>>s[i]>>t[i];
}
auto lca = [&](int x, int y){
if (check(x, y)) return x;
if (check(y, x)) return y;
for (int i = lg; i >= 0; i--){
if (!check(pw[x][i], y)){
x = pw[x][i];
}
}
return pw[x][0];
};
auto on = [&](int i, int j){
int l = lca(s[i], t[i]);
return check(l, s[j]) && (check(s[j], s[i]) || check(s[j], t[i]));
};
vector<int> f[m + 1];
for (int i = 1; i <= m; i++){
for (int j = 1; j <= m; j++){
if (i == j) continue;
if (on(i, j)){
f[i].pb(j);
}
}
}
vector<bool> used(m + 1);
vector<int> order;
function<void(int)> dfs = [&](int v){
used[v] = 1;
for (int i: f[v]){
if (!used[i]){
dfs(i);
}
}
order.pb(v);
};
for (int i = 1; i <= m; i++){
if (!used[i]){
dfs(i);
}
}
FT T(n);
vector<int> a(n + 1);
auto upd = [&](int v, int k){
a[v] += k;
T.upd(tin[v], tout[v], k);
};
for (int i = 1; i <= m; i++){
upd(s[i], 1);
}
auto get = [&](int x, int y){
int l = lca(x, y);
return T.get(tin[x]) + T.get(tin[y]) - 2 * T.get(tin[l]) + a[l];
};
bool out = 1;
for (int i: order){
if (get(s[i], t[i]) > 1){
out = 0;
break;
}
upd(s[i], -1);
upd(t[i], 1);
}
cout<<((out) ? "Yes" : "No")<<"\n";
}
}
# | 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... |