#include<bits/stdc++.h>
using namespace std;
const int maxn=120000+10,maxl=18;
vector<int>adj[maxn];
int n,m,timea=0,alln[maxn],lca[maxl][maxn],ted[maxn],high[maxn];
pair<int,int>allq[maxn],stf[maxn];
int zird(int u,int v){
return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}
int getlca(int u,int v){
if(zird(u,v)){
return v;
}
if(zird(v,u)){
return u;
}
for(int i=maxl-1;i>=0;i--){
if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
u=lca[i][u];
}
}
return lca[0][u];
}
void callca(){
for(int i=1;i<maxl;i++){
for(int j=1;j<=n;j++){
lca[i][j]=lca[i-1][lca[i-1][j]];
}
}
}
void dfs(int u=1,int par=0){
lca[0][u]=par;
timea++;
stf[u].first=timea;
for(auto x:adj[u]){
if(x!=par){
high[x]=high[u]+1;
dfs(x,u);
}
}
stf[u].second=timea;
}
void vorod(){
timea=0;
cin>>n;
// seg.clear();
for(int i=1;i<=n;i++){
adj[i].clear();
alln[i]=-1;
}
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cin>>m;
for(int i=1;i<=m;i++){
ted[i]=0;
cin>>allq[i].first>>allq[i].second;
alln[allq[i].first]=i;
alln[allq[i].second]=i;
}
}
int dis(int u,int v){
int uv=getlca(u,v);
return high[u]+high[v]-2*high[uv];
}
int din(int uv,int u,int v){
int a=dis(u,v),b=dis(uv,u),c=dis(uv,v);
//cout<<uv<<" "<<u<<" "<<v<<" "<<a<<" "<<b<<" "<<c<<endl;
if(b+c==a){
return 1;
}
return 0;
}
void psolve(){
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
if(i!=j){
//cout<<i<<" "<<j<<" wtf "<<allq[i].first<<" "<<allq[i].second<<" "<<allq[j].first<<" "<<allq[j].second<<"\n";
if(din(allq[j].first,allq[i].first,allq[i].second)){
ted[i]++;
}
if(din(allq[i].second,allq[j].first,allq[j].second)){
ted[i]++;
}
}
}
}
set<pair<int,int>>st;
for(int i=1;i<=m;i++){
//cout<<"now: "<<ted[i]<<" "<<i<<"\n";
st.insert(make_pair(ted[i],i));
}
while((int)st.size()>0){
auto x=*st.begin();
if(x.first!=0){
//cout<<x.first<<" "<<x.second<<endl;
cout<<"NO\n";
return ;
}
st.erase(x);
int i=x.second;
for(int j=1;j<=m;j++){
if(i!=j){
if(din(allq[i].first,allq[j].first,allq[j].second)){
st.erase(make_pair(ted[j],j));
ted[j]--;
st.insert(make_pair(ted[j],j));
}
if(din(allq[j].second,allq[i].first,allq[i].second)){
st.erase(make_pair(ted[j],j));
ted[j]--;
st.insert(make_pair(ted[j],j));
}
}
}
}
cout<<"YES\n";
return ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
for(int asd=0;asd<t;asd++){
vorod();
dfs();
callca();
psolve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
