fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. #include<bits/stdc++.h>
  6.  
  7. vector<vector<int>> adj;
  8. int arr[(int) 2e5 + 2];
  9. int dis[(int) 2e5 + 2];
  10. int n;
  11. queue<pair<int,int>>pq ;
  12. void bfs()
  13. {
  14.     while(!pq.empty())
  15.     {
  16.         auto pt = pq.front() ;
  17.         pq.pop() ;
  18.         if(pt.second>dis[pt.first])
  19.         {
  20.             continue;
  21.         }
  22.         dis[pt.first]=pt.second ;
  23.         for(auto child:adj[pt.first])
  24.         {
  25.             if(dis[child]<=pt.second)
  26.             {
  27.                 continue;
  28.             }
  29.             else
  30.             {
  31.                 pq.push({child,pt.second+1}) ;
  32.             }
  33.         }
  34.     }
  35. }
  36. bool dfs(int node,int par, int distance)
  37. {
  38.     if(dis[node]>distance&&node!=1&&adj[node].size()<=1)
  39.     {
  40.         return true ;
  41.     }
  42.     bool flag=false ;
  43.     for(auto child:adj[node])
  44.     {
  45.         if(par!=child)
  46.         {
  47.            flag|=dfs(child,node,distance+1) ;
  48.         }
  49.     }
  50.     return flag ;
  51. }
  52.  
  53. int main() {
  54.     int t;
  55.     cin >>
  56.         t;
  57.     while (t--) {
  58.         cin >> n;
  59.         adj.clear();
  60.  
  61.         adj.resize(n + 1);
  62.         for (int i = 1; i <= n; i++) {
  63.             dis[i] = 1e9;
  64.         }
  65.         int x;
  66.         cin >> x;
  67.         while(!pq.empty())
  68.         {
  69.             pq.pop() ;
  70.         }
  71.        for (int i = 0; i < x; i++) {
  72.             cin >> arr[i];
  73.             dis[arr[i]]=0 ;
  74.             pq.push({arr[i],0}) ;
  75.         }
  76.  
  77.         for (int i = 0; i < n - 1; i++) {
  78.             int u, v;
  79.             cin >> u >> v;
  80.             adj[u].push_back(v);
  81.             adj[v].push_back(u);
  82.         }
  83.         bfs() ;
  84.       if( dfs(1,-1,0) )
  85.       {
  86.           cout<<"YES"<<endl ;
  87.       }
  88.       else
  89.       {
  90.           cout<<"NO"<<endl ;
  91.       }
  92.  
  93.  
  94. /****************
  95.  * lets do it
  96.  */
  97.     }
  98. }
Success #stdin #stdout 0s 5560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CBAxuP
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!