Submission #1028823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028823		NeroZein	Cat Exercise (JOI23_ho_t4)	C++17	30 / 100	167 ms	54356 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define int long long

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int LOG = 18;
const int N = 2e5 + 5; 

int a[N];
int dep[N];
int up[LOG][N];
bool active[N];
vector<int> g[N];
long long ans[N];
int p[N], sz[N], mx[N];

void dfs(int v, int pr) {
  for (int u : g[v]) {
    if (u == pr) {
      continue; 
    }
    dep[u] = dep[v] + 1; 
    up[0][u] = v; 
    for (int j = 1; j < LOG; ++j) {
      up[j][u] = up[j - 1][up[j - 1][u]];
    }
    dfs(u, v);
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      u = up[j][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int j = LOG - 1; j >= 0; --j) {
    if (up[j][u] != up[j][v]) {
      u = up[j][u]; 
      v = up[j][v];
    }
  }
  return up[0][u];
}

int dist(int u, int v) {
  return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int get(int v) {
  return p[v] = (p[v] == v ? v : get(p[v]));
}

void unite(int u, int v) {
  u = get(u); v = get(v); 
  if (sz[u] > sz[v]) {
    swap(u, v);
  }
  p[u] = v;
  sz[v] += sz[u];
  int w = dist(mx[u], mx[v]);
  if (a[mx[v]] > a[mx[u]]) {
    ans[v] = max(ans[v], ans[u] + w);     
  } else {
    mx[v] = mx[u];
    ans[v] += w;
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 1); 
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 1);
  sort(ord.begin(), ord.end(), [&](int u, int v) {
    return a[u] < a[v];
  });
  for (int i = 1; i <= n; ++i) {
    p[i] = i;
    sz[i] = 1; 
    mx[i] = i; 
  }
  for (int v : ord) {
    for (int u : g[v]) {
      if (active[u]) {
        unite(u, v);        
      }
    }
    active[v] = true;
  }
  cout << ans[get(ord.back())] << '\n';
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 23 / 23
• Subtask 7: 0 / 26