fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define REP(i, n) for (int i = 0; i < (int)(n); ++i)
  8. typedef long long LL;
  9. typedef pair<int, int> PII;
  10.  
  11. int n, k, m;
  12. int a[200000];
  13. bool q[200000];
  14. vector<PII> g[200000];
  15. int d[400000];
  16. bool term[400000];
  17. int s[400000], t[400000];
  18.  
  19. void dfs(int v, int p, int ind) {
  20.     if (d[ind] != -1) return;
  21.     if (!q[v]) {
  22.         term[ind] = true;
  23.         d[ind] = 0;
  24.         return;
  25.     }
  26.     term[ind] = false;
  27.     int mxterm = 0;
  28.     int rest = 0;
  29.     for (PII to : g[v]) if (to.first != p) {
  30.         dfs(to.first, v, to.second);
  31.         if (term[to.second]) {
  32.             term[ind] = true;
  33.             mxterm = max(mxterm, d[to.second]);
  34.         } else {
  35.             rest += d[to.second];
  36.         }
  37.     }
  38.     d[ind] = 1 + mxterm + rest;
  39. }
  40.  
  41. bool solve(int x) {
  42.     REP(i, n) q[i] = a[i] >= x;
  43.     memset(d, -1, sizeof d);
  44.     memset(term, 0, sizeof term);
  45.     REP(i, m) if (d[i] == -1) {
  46.         dfs(t[i], s[i], i);
  47.     }
  48.     REP(i, n) if (q[i]) {
  49.         int mxterm = 0;
  50.         int rest = 0;
  51.         for (PII to : g[i]) {
  52.             if (term[to.second]) mxterm = max(mxterm, d[to.second]);
  53.             else rest += d[to.second];
  54.         }
  55.         if (1 + rest + mxterm >= k) return true;
  56.     }
  57.     return false;
  58. }
  59.  
  60. int main() {
  61.     //freopen("input.txt", "r", stdin);
  62.     scanf("%d%d", &n, &k);
  63.     REP(i, n) scanf("%d", a + i);
  64.     REP(i, n - 1) {
  65.         int from, to;
  66.         scanf("%d%d", &from, &to), --from, --to;
  67.         g[from].pb(mp(to, 2 * i));
  68.         g[to].pb(mp(from, 2 * i + 1));
  69.         s[2 * i] = from;
  70.         t[2 * i] = to;
  71.         s[2 * i + 1] = to;
  72.         t[2 * i + 1] = from;
  73.     }
  74.     m = 2 * n - 2;
  75.     int lo = 1, hi = 1000000, mid;
  76.     while (lo < hi) {
  77.         mid = (lo + hi + 1) >> 1;
  78.         if (solve(mid)) lo = mid;
  79.         else hi = mid - 1;
  80.     }
  81.     printf("%d\n", lo);
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 11816KB
comments (?)
stdin
copy 
5 3
3 6 1 4 2
1 2
2 4
2 5
1 3
stdout
copy 
3
https://ideone.com/d46vuQ
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!