fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pp push_back
  5. #define endl '\n'
  6. #define all(x) x.begin(),x.end()
  7. #define ld long double
  8. #define PI acos(-1)
  9. #define sin(a) sin((a)*PI/180)
  10. #define cos(a) cos((a)*PI/180)
  11. #define ones(x) __builtin_popcountll(x)
  12. //#define int ll
  13.  
  14. using namespace std;
  15.  
  16. void Drakon() {
  17.     ios_base::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.     cout.tie(nullptr);
  20. #ifdef Clion
  21.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  22. #endif
  23. }
  24.  
  25. unsigned long long inf = 1e10;
  26. const double EPS = 1e-6;
  27. const int MOD = 1000000007, N = 200005, LOG = 25;
  28.  
  29. ll mul(const ll &a, const ll &b) {
  30.     return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
  31. }
  32.  
  33. ll add(const ll &a, const ll &b) {
  34.     return (a + b + 2 * MOD) % MOD;
  35. }
  36.  
  37. ll pw(ll x, ll y) {
  38.     ll ret = 1;
  39.     while (y > 0) {
  40.         if (y % 2 == 0) {
  41.             x = mul(x, x);
  42.             y = y / 2;
  43.         } else {
  44.             ret = mul(ret, x);
  45.             y = y - 1;
  46.         }
  47.     }
  48.     return ret;
  49. }
  50.  
  51. struct seg {
  52.     int len = 0;
  53.  
  54.     seg() {
  55.  
  56.     }
  57.  
  58.     seg(int len) {
  59.         this->len = len;
  60.     }
  61. };
  62.  
  63. struct segtree {
  64.  
  65.     vector<seg> values;
  66.     int size = 1, n;
  67.  
  68.     void init(int nn) {
  69.         n = nn;
  70.         while (size < nn)size *= 2;
  71.         values.resize(2 * size, seg());
  72.     }
  73.  
  74.     seg mrg(seg &a, seg &b) {
  75.         seg c;
  76.         c.len = max(a.len, b.len);
  77.         return c;
  78.     }
  79.  
  80.     void update(int i, int v, int x, int lx, int rx) {
  81.  
  82.         if (lx == rx) {
  83.             if(v == -1) values[x].len = 0;
  84.             else values[x].len = max(values[x].len, v);
  85.             return;
  86.         }
  87.         int mid = (lx + rx) / 2;
  88.         if (i <= mid)
  89.             update(i, v, 2 * x + 1, lx, mid);
  90.         else
  91.             update(i, v, 2 * x + 2, mid + 1, rx);
  92.         values[x] = mrg(values[2 * x + 1], values[2 * x + 2]);
  93.     }
  94.  
  95.     void update(int i, int v) {
  96.         update(i, v, 0, 0, n - 1);
  97.     }
  98.  
  99.     seg query(int l, int r, int x, int lx, int rx) {
  100.  
  101.         if (l > rx || lx > r) {
  102.             return seg();
  103.         }
  104.         else if (lx >= l && rx <= r) {
  105.             return values[x];
  106.         }
  107.  
  108.         int mid = (lx + rx) / 2;
  109.         seg s1 = query(l, r, 2 * x + 1, lx, mid);
  110.         seg s2 = query(l, r, 2 * x + 2, mid + 1, rx);
  111.         return mrg(s1, s2);
  112.     }
  113.  
  114.     seg query(int l, int r) {
  115.         return query(l, r, 0, 0, n - 1);
  116.     }
  117.  
  118. };
  119.  
  120. vector<int> adj[N];
  121. int n, sz[N], big[N];
  122.  
  123. void dfsSz(int u, int par) {
  124.     sz[u] = 1;
  125.     for (auto &v: adj[u]) {
  126.         if (v == par)continue;
  127.         dfsSz(v, u);
  128.         sz[u] += sz[v];
  129.         if (big[u] == -1 || sz[v] > sz[big[u]])
  130.             big[u] = v;
  131.     }
  132. }
  133.  
  134. segtree nhaya, bdaya;
  135. int ans, startNode[N], endNode[N], s[N];
  136. vector<pair<int, pair<int, int>>> vec;
  137.  
  138. void collect(int u, int par, int val, int bestNhaya, int bestBdaya) {
  139.  
  140.     // start
  141.     if(s[u] > val) {
  142.         ans = max(ans, bestNhaya + 1 + startNode[u]);
  143.     }
  144.     // end
  145.     if(s[u] < val) {
  146.         ans = max(ans, endNode[u] + 1 + bestBdaya);
  147.     }
  148.  
  149.     ans = max(ans, endNode[u] + bdaya.query(s[u] + 1, N - 1).len);
  150.     ans = max(ans, nhaya.query(0, s[u] - 1).len + startNode[u]);
  151.  
  152.     vec.push_back({s[u], {startNode[u], endNode[u]}});
  153.  
  154.     for (auto v: adj[u]) {
  155.         if (v == par)continue;
  156.         collect(v, u, val, bestNhaya, bestBdaya);
  157.     }
  158. }
  159.  
  160. void reset(int u, int par) {
  161.     bdaya.update(s[u], -1);
  162.     nhaya.update(s[u], -1);
  163.     for (auto v: adj[u]) {
  164.         if (v == par)continue;
  165.         reset(v, u);
  166.     }
  167. }
  168.  
  169. void dfs(int u, int par, bool keep) {
  170.     for (auto v: adj[u]) {
  171.         if (v == par || v == big[u])continue;
  172.         dfs(v, u, false);
  173.     }
  174.     if (~big[u]) {
  175.         dfs(big[u], u, true);
  176.     }
  177.  
  178.  
  179.     for (auto v: adj[u]) {
  180.         if (v == par || v == big[u])continue;
  181.         vec.clear();
  182.  
  183.         collect(v, u, s[u], nhaya.query(0, s[u] - 1).len, bdaya.query(s[u] + 1, N - 1).len);
  184.         for(auto val : vec) {
  185.             bdaya.update(val.first, val.second.first);
  186.             nhaya.update(val.first, val.second.second);
  187.         }
  188.     }
  189.  
  190.     startNode[u] = bdaya.query(s[u] + 1, N - 1).len + 1;
  191.     endNode[u] = nhaya.query(0, s[u] - 1).len + 1;
  192.  
  193.     ans = max(ans, startNode[u]);
  194.     ans = max(ans, endNode[u]);
  195.  
  196.     bdaya.update(s[u], startNode[u]);
  197.     nhaya.update(s[u], endNode[u]);
  198.  
  199.     // reset
  200.     if (!keep) {
  201.         reset(u, par);
  202.     }
  203. }
  204.  
  205. void solve() {
  206.     cin >> n;
  207.     for (int i = 0; i < n; ++i) {
  208.         cin >> s[i];
  209.     }
  210.     for (int i = 0; i < n - 1; ++i) {
  211.         int u, v;
  212.         cin >> u >> v;
  213.         u--, v--;
  214.         adj[u].push_back(v);
  215.         adj[v].push_back(u);
  216.     }
  217.  
  218.     memset(big, -1, sizeof big);
  219.     dfsSz(0, 0);
  220.     bdaya.init(N);
  221.     nhaya.init(N);
  222.     dfs(0, 0, true);
  223.  
  224.     cout << ans;
  225. }
  226.  
  227. signed main() {
  228.     Drakon();
  229.     int t = 1;
  230.     //cin >> t;
  231.     while (t--) {
  232.         solve();
  233.     }
  234. }
Success #stdin #stdout 0.01s 14600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/nhaOPx
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

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!