YEZAELP

SMMR-143: Story of Pleng

Apr 14th, 2021 (edited)
144
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.74 KB | None
  1. /*
  2. dp on graph
  3. undirected graph
  4. */
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8. const int INF = 2e9;
  9. const int N = 1e5;
  10. vector <int> g[N+10];
  11. int dp1[N+10], dp2[N+10];
  12. bool visited[N+10], p[N+10];
  13. int mx = 0, node;
  14.  
  15. int f(int u){
  16.     if(visited[u]) return -INF;
  17.     visited[u] = true;
  18.     for(auto v: g[u]){
  19.         if(visited[v]) continue;
  20.         int dis = f(v) + 1;
  21.         if(dis > dp1[u]){
  22.             dp2[u] = dp1[u];
  23.             dp1[u] = dis;
  24.         }
  25.         else dp2[u] = max(dp2[u], dis);
  26.     }
  27.     if(dp1[u] + dp2[u] - 1 > mx){
  28.         mx = dp1[u] + dp2[u] - 1;
  29.         node = u;
  30.     }
  31.     return dp1[u];
  32. }
  33.  
  34. void prt2(int u, int d){
  35.     if(d == 0) return;
  36.     for(auto v: g[u]){
  37.         if(v == u) continue;
  38.         if(dp1[v] == d-1) {
  39.             prt2(v, d-1);
  40.             printf("%d ", u);
  41.             p[u] = true;
  42.             return;
  43.         }
  44.     }
  45.     printf("%d ", u);
  46.     p[u] = true;
  47. }
  48.  
  49. void prt1(int u, int d){
  50.     if(u != node) printf("%d ", u);
  51.     for(auto v: g[u]){
  52.         if(v == u) continue;
  53.         if(dp1[v] == d-1 and !p[v]){
  54.             prt1(v, d-1);
  55.             return;
  56.         }
  57.     }
  58. }
  59.  
  60. int main(){
  61.  
  62.     int n;
  63.     scanf("%d", &n);
  64.  
  65.     for(int i=1;i<=n;i++){
  66.         dp1[i] = 1;
  67.     }
  68.  
  69.     for(int i=1;i<n;i++){
  70.         int u, v;
  71.         scanf("%d%d", &u, &v);
  72.         g[u].push_back(v);
  73.         g[v].push_back(u);
  74.     }
  75.  
  76.     f(1);
  77.  
  78.     printf("%d\n", mx);
  79.  
  80.     prt2(node, dp2[node]);
  81.     prt1(node, dp1[node]);
  82.  
  83.     return 0;
  84. }
  85. /***
  86. 10
  87. 1 2
  88. 2 3
  89. 3 4
  90. 4 5
  91. 5 6
  92. 6 7
  93. 7 8
  94. 2 9
  95. 9 10
  96.  
  97. 5
  98. 1 2
  99. 2 3
  100. 2 4
  101. 2 5
  102.  
  103. 4
  104. 1 2
  105. 2 3
  106. 3 4
  107.  
  108. 21
  109. 1 2
  110. 2 3
  111. 2 6
  112. 3 4
  113. 3 5
  114. 6 7
  115. 6 8
  116. 8 9
  117. 8 14
  118. 9 10
  119. 9 11
  120. 11 12
  121. 11 13
  122. 14 15
  123. 14 19
  124. 15 16
  125. 15 17
  126. 15 18
  127. 19 20
  128. 20 21
  129. ***/
  130.  
RAW Paste Data Copied