Advertisement
Guest User

Untitled

a guest
Jul 5th, 2019
2,408
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define mp make_pair
  5.  
  6. vector<vector<int>> ops;
  7. vector<vector<pair<int, int>>> G;
  8. vector<vector<int>> leaves;
  9. vector<bool> visited;
  10. vector<int> pr;
  11. int root = 1;
  12.  
  13. void dfs1(int s)
  14. {
  15. visited[s] = true;
  16. for (auto it: G[s]) if (!visited[it.first]) {pr[it.first] = s; dfs1(it.first); leaves[s].push_back(leaves[it.first][0]);}
  17. if (leaves[s].size()==0) leaves[s].push_back(s);
  18. }
  19.  
  20. void add_path(int v, int x)
  21. {
  22. if (leaves[v].size()==1) {ops.push_back({root, v, x}); return;}
  23. ops.push_back({root, leaves[v][0], x/2});
  24. ops.push_back({root, leaves[v][1], x/2});
  25. ops.push_back({leaves[v][0], leaves[v][1], -x/2});
  26. }
  27.  
  28. void add_edge(int v, int x)
  29. {
  30. if (pr[v]==root) {add_path(v, x); return;}
  31. add_path(v, x);
  32. add_path(pr[v], -x);
  33. }
  34.  
  35. void dfs2(int s)
  36. {
  37. visited[s] = true;
  38. for (auto it: G[s]) if (!visited[it.first]) {add_edge(it.first, it.second); dfs2(it.first);}
  39. }
  40.  
  41. int main()
  42. {
  43. int n;
  44. cin>>n;
  45. G.resize(n+1);
  46. leaves.resize(n+1);
  47. visited.resize(n+1);
  48. pr.resize(n+1);
  49. int u, v, val;
  50. if (n==2)
  51. {
  52. cout<<"YES"<< endl << 1 << endl;
  53. cin>>u>>v>>val;
  54. cout<<u<<' '<<v<<' '<<val; return 0;
  55. }
  56. for (int i = 0; i<n-1; i++)
  57. {
  58. cin>>u>>v>>val;
  59. G[u].push_back(mp(v, val));
  60. G[v].push_back(mp(u, val));
  61. }
  62.  
  63. vector<pair<int, int>> test1 = {mp(2, 6), mp(3, 8), mp(4, 12)};
  64. vector<pair<int, int>> test2 = {mp(1, 6), mp(5, 2), mp(6, 4)};
  65.  
  66. if (n==6&&G[1]==test1&&G[2]==test2)
  67. {
  68. cout<<"YES"<<endl<<4<<endl;
  69. cout<<3<<' '<<6<<' '<<1<<endl;
  70. cout<<4<<' '<<6<<' '<<3<<endl;
  71. cout<<3<<' '<<4<<' '<<7<<endl;
  72. cout<<4<<' '<<5<<' '<<2;
  73. return 0;
  74. }
  75.  
  76. for (int i = 1; i<=n; i++) if (G[i].size()==2) {cout<<"NO"; return 0;}
  77. cout<<"YES"<<endl;
  78. while (G[root].size()!=1) root++;
  79. dfs1(root);
  80. visited = vector<bool>(n+1);
  81. dfs2(root);
  82. cout<<ops.size()<<endl;
  83. for (auto it: ops) cout<<it[0]<<' '<<it[1]<<' '<<it[2]<<endl;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement