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>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
vector<vector<int>> g,ng;
vector<int> s,t,dep,jump[18],in,out;
int tme=0;
struct BIT{
int n,m;
vector<vector<int>> b;
BIT(int _n,int _m):n(_n),m(_m){
b.resize(n+1,vector<int>(m));
}
void add(int x,int k,int val){
for(int i=x;i<=n;i+=i&-i){
b[i][k]+=val;
}
}
vector<int> qry(int x){
vector<int> ret(m);
for(int i=x;i>0;i-=i&-i){
for(int j=0;j<m;j++){
ret[j]+=b[i][j];
}
}
return ret;
}
};
void dfs(int pre,int pos){
in[pos]=tme;
tme++;
for(int i:g[pos]){
if(i==pre) continue;
dep[i]=dep[pos]+1;
jump[0][i]=pos;
dfs(pos,i);
}
out[pos]=tme;
tme++;
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int dif=dep[x]-dep[y],cnt=0;//cout<<x<<' '<<y<<' '<<dif<<endl;
while(dif){
if(dif&1) x=jump[cnt][x];
cnt++;
dif>>=1;
}//cout<<x<<' '<<y<<endl;
if(x==y) return x;
for(int i=17;i>=0;i--){
if(jump[i][x]!=jump[i][y]){
x=jump[i][x];
y=jump[i][y];
}//cout<<x<<' '<<y<<endl;
}
return jump[0][x];
}
vector<int> merge(vector<int> x,vector<int> y,int c){//cout<<"ok"<<endl;
//for(int i:x) cout<<i<<' ';cout<<endl;for(int i:y) cout<<i<<' ';cout<<endl;
for(int i=0;i<x.size();i++){
x[i]+=y[i]*c;
}
//for(int i:x) cout<<i<<' ';cout<<endl;
return x;
}
vector<int> search(int x,int y,BIT *Bit){
vector<int> ret;
int LCA=lca(x,y);//cout<<LCA<<endl;
ret=merge(Bit->qry(in[x]+1),Bit->qry(in[y]+1),1);
ret=merge(ret,Bit->qry(in[LCA]+1),-1);
ret=merge(ret,Bit->qry(in[LCA]),-1);//for(int i:ret) cout<<i<<' ';cout<<endl;
return ret;
}
void insert(int x,BIT *Bit){
Bit->add(in[x]+1,x,1);
Bit->add(out[x]+1,x,-1);
}
signed main(){
int tt;
cin>>tt;
while(tt--){
tme=0;
int n;
cin>>n;
g.clear();
ng.clear();
for(auto &i:jump){
i.resize(n,0);
}
dep.resize(n,0);
g.resize(n);
in.resize(n);
out.resize(n);
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
int m;
cin>>m;
ng.resize(m);
s.resize(m);
t.resize(m);
dfs(0,0);
for(int i=1;i<18;i++){
for(int j=0;j<n;j++){
jump[i][j]=jump[i-1][jump[i-1][j]];
}
}
BIT bits(n*2,m),bitt(n*2,m);
for(int i=0;i<m;i++){
cin>>s[i]>>t[i];
s[i]--;
t[i]--;//cout<<s[i]<<' '<<t[i]<<endl;
}
vector<int> du(m);
for(int i=0;i<m;i++){
vector<int> tmp1=search(s[i],t[i],&bits),tmp2=search(s[i],t[i],&bitt);
//for(int j:tmp1) cout<<j<<' ';cout<<endl;
for(int j=0;j<m;j++){
if(tmp1[j]){
ng[i].push_back(j);
du[j]++;
}
if(tmp2[j]){
ng[j].push_back(i);
du[i]++;
}
}
insert(i,&bits);
insert(i,&bitt);
}
queue<int> q;
for(int i=0;i<m;i++){
if(!du[i]) q.push(i);
}
while(!q.empty()){
int pos=q.front();
q.pop();
for(int i:ng[pos]){
du[i]--;
if(!du[i]) q.push(i);
}
}
int ans=1;
for(int i=0;i<m;i++){
if(du[i]) ans=0;
}
if(ans) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
Compilation message (stderr)
jail.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>, long long int)':
jail.cpp:62:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
# | 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... |