Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdio.h>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <set>
  7. #include <cstring>
  8. #include <assert.h>
  9. #include <cstdlib>
  10. #include <cmath>
  11. #include <queue>
  12.  
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16.  
  17. const ll INF = 1e9, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
  18.  
  19. int n, dp[200000][2], di[200000], ans[200000];
  20.  
  21. vector <int> g[200000], ind[200000];
  22.  
  23. void merge (int& mx, int& sec, int a) {
  24.     if (mx <= a) {
  25.         sec = mx;
  26.         mx = a;
  27.     }
  28.     else sec = max (sec, a);
  29. }
  30.  
  31. void dp_dfs (int x, int p) {
  32.     vector <int> v, id;
  33.     for (int i = 0; i < g[x].size (); i++) {
  34.         if (g[x][i] != p) {
  35.             v.push_back (g[x][i]);
  36.             id.push_back (ind[x][i]);
  37.         }
  38.     }
  39.     g[x] = v;
  40.     ind[x] = id;
  41.     v.clear ();
  42.     id.clear ();
  43.  
  44.     for (int to : g[x]) {
  45.         dp_dfs (to, x);
  46.         merge (dp[x][0], dp[x][1], dp[to][0] + 1);
  47.  
  48.         di[x] = max (di[to], di[x]);
  49.     }
  50.     di[x] = max (di[x], dp[x][0] + dp[x][1]);
  51. }
  52.  
  53. void dfs (int x, int p, int mx, int di_up) {
  54.     if (g[x].empty ()) return;
  55.     vector <int> s[2], s_d (g[x].size ());
  56.     s[0].resize (g[x].size ());
  57.     s[1].resize (g[x].size ());
  58.  
  59.     s[0][g[x].size () - 1] = dp[g[x].back ()][0] + 1;
  60.     s_d[g[x].size () - 1] = di[g[x].back ()];
  61.  
  62.     for (int i = g[x].size () - 2; i >= 0; i--) {
  63.         int to = g[x][i];
  64.         s[0][i] = s[0][i+1];
  65.         s[1][i] = s[1][i+1];
  66.         merge (s[0][i], s[1][i], dp[to][0] + 1);
  67.  
  68.         s_d[i] = max (di[to], s_d[i+1]);
  69.     }
  70.  
  71.     int pref[2] = {0, 0}, pref_d = 0;
  72.  
  73.     for (int i = 0; i < g[x].size (); i++) {
  74.         int to = g[x][i];
  75.         int cur[2] = {pref[0], pref[1]}, cur_d = pref_d;
  76.  
  77.         if (i != g[x].size () - 1) {
  78.             merge (cur[0], cur[1], s[0][i+1]);
  79.             merge (cur[0], cur[1], s[1][i+1]);
  80.  
  81.             cur_d = max (cur_d, s_d[i+1]);
  82.         }
  83.  
  84.         int best_diam = max (di_up, max (max (mx, cur[1]) + cur[0], cur_d));
  85.  
  86.         ans[ind[x][i]] = 1 + di[to] + best_diam;
  87.         dfs (to, x, max (mx + 1, cur[0] + 1), best_diam);
  88.  
  89.         merge (pref[0], pref[1], dp[to][0] + 1);
  90.         pref_d = max (pref_d, di[to]);
  91.     }
  92.  
  93.     s[0].clear ();
  94.     s[1].clear ();
  95.     s_d.clear ();
  96. }
  97.  
  98. int main () {
  99.     ifstream fin ("plimbare3.in");
  100.     ofstream fout ("plimbare3.out");
  101.    
  102.     fin >> n;
  103.  
  104.     for (int i = 0; i < n - 1; i++) {
  105.         int u, v;
  106.  
  107.         fin >> u >> v;
  108.  
  109.         g[u-1].push_back (v - 1);
  110.         ind[u-1].push_back (i);
  111.         g[v-1].push_back (u - 1);
  112.         ind[v-1].push_back (i);
  113.     }
  114.  
  115.     dp_dfs (0, -1);
  116.     dfs (0, -1, 0, 0);
  117.  
  118.     for (int i = 0; i < n - 1; i++)
  119.         fout << ans[i] << endl;
  120. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement