Advertisement
Guest User

Untitled

a guest
Aug 29th, 2015
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.39 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <iostream>
  7. #include <string>
  8. #include <vector>
  9. #define SZ(x) ((int)(x).size())
  10. #define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
  11. using namespace std;
  12. typedef long long LL;
  13.  
  14. const int N = 1e5+5;
  15. vector<int> a[N];
  16. int mark[N], mark2[N];
  17.  
  18. int getparent(int x, int y) {
  19. if (SZ(a[x]) == 1) {
  20. return y == -1? a[x][0] : 0;
  21. }
  22. if (SZ(a[x]) == 2) {
  23. return y == -1? 0 : a[x][0] + a[x][1] - y;
  24. }
  25. return 0;
  26. }
  27.  
  28. int main(void) {
  29. int n;
  30. scanf("%d", &n);
  31. for(int i=1;i<n;i++) {
  32. int x, y;
  33. scanf("%d%d", &x, &y);
  34. a[x].push_back(y);
  35. a[y].push_back(x);
  36. }
  37. for(int i=1;i<=n;i++) {
  38. if(SZ(a[i])==1 && mark[i]==0) {
  39. int x = i, y = -1, z;
  40. mark[x] = 1;
  41. while ((z = getparent(x, y)) > 0) {
  42. if(SZ(a[z]) > 2) break;
  43. mark[z] = 1;
  44. y = x;
  45. x = z;
  46. }
  47. }
  48. }
  49. int d[3]={}, ok = 1;
  50. for(int i=1;i<=n;i++) {
  51. if (mark[i]==0) {
  52. int deg=0;
  53. FOR(it, a[i]) if(mark[*it]==0) ++deg;
  54. if (deg==1 && SZ(a[i])<=3) mark2[i] = 1;
  55. }
  56. }
  57. for(int i=1;i<=n;i++) mark[i] |= mark2[i];
  58. for(int i=1;i<=n;i++) {
  59. if (mark[i]==0) {
  60. int deg=0;
  61. FOR(it, a[i]) if(mark[*it]==0) ++deg;
  62. if (deg<=2) ++d[deg];
  63. else ok=0;
  64. }
  65. }
  66. if(d[1]>2) ok = 0;
  67. puts(ok? "Yes":"No");
  68. return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement