fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void fast(){
  5.     ios_base::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     cout.tie(nullptr);
  8. }
  9.  
  10. const int N = 200005;
  11. vector<int> adj[N];
  12. int vis[N];
  13. int in[N];
  14. bool bad = false;
  15.  
  16. void dfs(int node){
  17.     vis[node] = 1;
  18.     int cnt = 0;
  19.     for(auto ch : adj[node]){
  20.         if(vis[ch] == 0){
  21.             cnt++;
  22.         }
  23.     }
  24.     if(cnt > 2) bad = true;
  25.     for(auto ch : adj[node]){
  26.         if(vis[ch] == 0){
  27.             dfs(ch);
  28.         }
  29.     }
  30. }
  31.  
  32. int main(){
  33.     fast();
  34.     int t;
  35.     cin >> t;
  36.     while(t--){
  37.         int n;
  38.         cin >> n;
  39.  
  40.         for (int i = 1; i <= n; ++i) {
  41.             adj[i].clear();
  42.             vis[i] = 0;
  43.             in[i] = 0;
  44.         }
  45.         bad = false;
  46.  
  47.         for (int i = 0; i < n - 1; ++i) {
  48.             int u, v;
  49.             cin >> u >> v;
  50.             adj[u].push_back(v);
  51.             adj[v].push_back(u);
  52.             in[u]++;
  53.             in[v]++;
  54.         }
  55.  
  56.         int leaf = 0;
  57.  
  58.         for (int i = 1; i <= n; ++i) {
  59.             if(in[i] == 1){
  60.                 leaf = i;
  61.                 break;
  62.             }
  63.         }
  64.  
  65.         dfs(leaf);
  66.  
  67.         if(bad){
  68.             cout << "NO" << endl;
  69.         } else {
  70.             cout << "YES" << endl;
  71.         }
  72.     }
  73.  
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 9204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
YES
https://ideone.com/umWaZV
language:
C++ (gcc 8.3)
created:
170 days ago
visibility:
secret

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!