| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1189228 | patgra | Cat Exercise (JOI23_ho_t4) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
int n, tb, maxLog;
vector<int> perm;
vector<pair<int, int>> t;
vector<int> lz;
vector<vector<int>> g;
vector<int> depth, subsz, preord;
int pre_t;
ll ans, curAns;
vector<vector<int>> stMin;
vector<int> euDep, firstInEu;
void tAdd(int l, int r, int x) {
DC << " tAdd(" << l << ' ' << r << ' ' << x << ")" << eol;
l += tb; r += tb;
t[l].first += x;
if(r != l) t[r].first += x;
while(l / 2 != r / 2) {
if(l % 2 == 0) t[l + 1].first += x, lz[l + 1] += x;
if(r % 2 == 1) t[r - 1].first += x, lz[r - 1] += x;
l /= 2;
r /= 2;
t[l] = max(t[2 * l], t[2 * l + 1]);
t[l].first += lz[l];
t[r] = max(t[2 * r], t[2 * r + 1]);
t[r].first += lz[r];
}
l /= 2;
while(l) t[l] = max(t[2 * l], t[2 * l + 1]), t[l].first += lz[l], l /= 2;
}
void dfs(int v, int p) {
depth[v] = depth[p] + 1;
subsz[v] = 1;
preord[v] = pre_t++;
firstInEu[v] = (int)euDep.size();
euDep.pb(depth[v]);
repIn(u, g[v]) if(u != p) dfs(u, v), euDep.pb(depth[v]), subsz[v] += subsz[u];
}
int stMinQ(int l, int r) {
if(l > r) swap(l, r);
int k = 31 - __builtin_clz(r - l + 1);
return min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
}
int dist(int a, int b) {
auto ret = depth[a] + depth[b] - 2 * stMinQ(firstInEu[a], firstInEu[b]);
DC << " dist(" << a << ' ' << b << ") = " << ret << eol;
return ret;
}
void reku(int v, int anc) {
if(anc) curAns += dist(v, anc);
DC << " -> (" << v << ' ' << anc << ") ans " << curAns << eol;
ans = max(ans, curAns);
repIn(u, g[v]) {
if(depth[u] < depth[v]) {
tAdd(preord[v], preord[v] + subsz[v] - 1, -1);
if(t[1].first == 0) reku(t[1].second, v);
tAdd(preord[v], preord[v] + subsz[v] - 1, 1);
}
else {
tAdd(0, n - 1, -1);
tAdd(preord[u], preord[u] + subsz[u] - 1, 1);
if(t[1].first == 0) reku(t[1].second, v);
tAdd(0, n - 1, 1);
tAdd(preord[u], preord[u] + subsz[u] - 1, -1);
}
}
if(anc) curAns -= dist(v, anc);
DC << " <- (" << v << ' ' << anc << ")" << eol;
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
perm.resize(n + 1);
depth.resize(n + 1);
subsz.resize(n + 1);
preord.resize(n + 1);
firstInEu.resize(n + 1);
g.resize(n + 1);
tb = 1 << (32 - __builtin_clz(n - 1));
t.resize(2 * tb);
lz.resize(2 * tb);
rep(i, 0, n) cin >> perm[i + 1];
rep(i, 1, n) {
int a, b;
cin >> a >> b;
a = perm[a], b = perm[b];
DC << a << ' ' << b << eol;
g[a].pb(b);
g[b].pb(a);
}
dfs(n, 0);
rep(i, 1, n + 1) t[preord[i] + tb].second = i;
rep(i, n, tb) t[i + tb].first = -1;
repD(i, tb - 1, 0) t[i] = max(t[2 * i], t[2 * i + 1]);
maxLog = 32 - __builtin_clz((int)euDep.size());
stMin.resize(euDep.size(), vector<int>(maxLog, 1e9));
rep(i, 0, (int)euDep.size()) stMin[i][0] = euDep[i];
rep(k, 1, maxLog) rep(i, 0, (int)stMin.size()) stMin[i][k] = min(stMin[i][k - 1], stMin[min((int)stMin.size() - 1, i + (1ll << (k - 1)))][k - 1]);
reku(n, 0);
cout << ans << '\n';
}