fork download
  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
stdin
Standard input is empty
stdout
YES
YES