Advertisement
K_Y_M_bl_C

Untitled

Dec 14th, 2016
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1.  
  2. const int Q = (int)2e5 + 7;
  3.  
  4. int n;
  5. ll w[Q];
  6.  
  7. vi g[Q];
  8. vll mxdst[Q];
  9. ll ww[Q];
  10.  
  11. ll ans = -LINF;
  12.  
  13. void dfs1(int u)
  14. {
  15.     mxdst[u].resize(g[u].size());
  16.     for (int i = 0; i < g[u].size(); ++i)
  17.     {
  18.         dfs1(g[u][i]);
  19.         mxdst[u][i] = ww[g[u][i]];
  20.     }
  21.     ww[u] = w[u];
  22.     for (int i = 0; i < g[u].size(); ++i)
  23.     {
  24.         ww[u] += mxdst[u][i];
  25.     }
  26. }
  27.  
  28. void dfs2(int u)
  29. {
  30.     for (int i = 0; i < g[u].size(); ++i)
  31.     {
  32.         dfs2(g[u][i]);
  33.         ww[u] = max(ww[g[u][i]], ww[u]);
  34.     }
  35. }
  36.  
  37. void dfs3(int u)
  38. {
  39.     vll rs;
  40.     for (int i = 0; i < g[u].size(); ++i)
  41.         dfs3(g[u][i]);
  42.     for (int i = 0; i < g[u].size(); ++i)
  43.         rs.inb(ww[g[u][i]]);
  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 == -LINF)
  67.         puts("Impossible");
  68.     else
  69.         cout << ans;
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement