Advertisement
K_Y_M_bl_C

Untitled

Dec 14th, 2016
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. const int Q = (int)2e5 + 7;
  2.  
  3. int n;
  4. ll w[Q];
  5.  
  6. vi g[Q];
  7. vll mxdst[Q];
  8. ll ww[Q];
  9.  
  10. ll ans = -1;
  11.  
  12. void dfs1(int u)
  13. {
  14.     mxdst[u].resize(g[u].size());
  15.     for (int i = 0; i < g[u].size(); ++i)
  16.     {
  17.         dfs1(g[u][i]);
  18.         mxdst[u][i] = ww[g[u][i]];
  19.     }
  20.     ww[u] = w[u];
  21.     for (int i = 0; i < g[u].size(); ++i)
  22.     {
  23.         ww[u] += mxdst[u][i];
  24.     }
  25. }
  26.  
  27. void dfs2(int u)
  28. {
  29.     for (int i = 0; i < g[u].size(); ++i)
  30.     {
  31.         dfs2(g[u][i]);
  32.         ww[u] = max(ww[g[u][i]], ww[u]);
  33.     }
  34. }
  35.  
  36. void dfs3(int u)
  37. {
  38.     vll rs;
  39.     for (int i = 0; i < g[u].size(); ++i)
  40.     {
  41.         dfs3(g[u][i]);
  42.         rs.inb(ww[g[u][i]]);
  43.     }
  44.     if (rs.size() > 1)
  45.     {
  46.         sort(all(rs));
  47.         ans = max(rs[rs.size() - 2] + rs[rs.size() - 1], ans);
  48.     }
  49. }
  50.  
  51. int solve()
  52. {
  53.     scanf("%d", &n);
  54.     for (int i = 0; i < n; ++i)
  55.         scanf("%lld", &w[i]);
  56.     for (int i = 0; i < n - 1; ++i)
  57.     {
  58.         int x, y;
  59.         scanf("%d %d", &x, &y);
  60.         --x, --y;
  61.         g[x].inb(y);
  62.     }
  63.     dfs1(0);
  64.     dfs2(0);
  65.     dfs3(0);
  66.     if (ans == -1)
  67.         puts("Impossible");
  68.     else
  69.         cout << ans;
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement