#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;
template<class T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
#ifdef __APPLE__
#include "debug.h"
#else
#define debug(...) 42
#endif
vector<vector<int>> g;
constexpr int k = 18;
vector<vector<int>> up;
vector<int> tin, tout, depth;
int timer = 0;
void dfs1(int v, int p) {
tin[v] = timer++;
if (p != -1) {
depth[v] = depth[p] + 1;
up[0][v] = p;
for (int i = 1; i < k; ++i) {
up[i][v] = up[i - 1][up[i - 1][v]];
}
}
for (auto u : g[v]) {
if (u != p) {
dfs1(u, v);
}
}
tout[v] = timer;
}
bool is_anc(int p, int v) {
return tin[p] <= tin[v] && tout[v] <= tout[p];
}
int up_d(int v, int d) {
for (int i = k - 1; i >= 0; --i) {
if (d >= (1 << i)) {
v = up[i][v];
d -= (1 << i);
}
}
return v;
}
int LCA(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
u = up_d(u, depth[u] - depth[v]);
for (int i = k - 1; i >= 0; --i) {
if (up[i][u] != up[i][v]) {
u = up[i][u];
v = up[i][v];
}
}
if (u == v) {
return u;
}
return up[0][u];
}
int ans = -1;
int ansi = -1, ansj = -1;
void ckans(int u, int v, int c) {
if (ans < c) {
ans = c;
ansi = u;
ansj = v;
}
}
vector<array<int, 3>> paths;
vector<vector<int>> p1, p2; // eblany, vertical
vector<pair<int, int>> mn1, mn2; // depth and path (for vertical)
void ckmn(int v, pair<int, int> x) {
if (x.first <= mn1[v].first) {
mn2[v] = mn1[v];
mn1[v] = x;
} else if (x.first <= mn2[v].first) {
mn2[v] = x;
}
}
multiset<array<int, 3>> dfs2(int v, int p) {
for (auto i : p2[v]) {
int j = paths[i][2];
ckmn(v, {depth[j], i});
}
multiset<array<int, 3>> cur;
auto upd = [&](int i) {
int b = paths[i][1], lca = paths[i][2];
{
auto it = cur.lower_bound(array<int, 3>{lca, tin[b], -1});
if (it != cur.end() && (*it)[0] == lca && (*it)[1] < tout[b]) {
ckans(i, (*it)[2], depth[v] + depth[b] - 2 * depth[lca]);
}
}
for (int j = k - 1; j >= 0; --j) {
int subtr = up[j][b];
if (depth[subtr] >= depth[lca]) {
auto it = cur.lower_bound(array<int, 3>{lca, tin[subtr], -1});
if (it == cur.end() || (*it)[0] != lca || (*it)[1] >= tout[subtr]) {
b = up[j][b];
}
}
}
if (b != lca) {
b = up[0][b];
auto it = cur.lower_bound(array<int, 3>{lca, tin[b], -1});
assert(it != cur.end() && (*it)[0] == lca && (*it)[1] < tout[b]);
ckans(i, (*it)[2], depth[v] + depth[b] - 2 * depth[lca]);
}
};
for (auto i : p1[v]) {
upd(i);
int j = paths[i][1];
cur.insert({paths[i][2], tin[j], i});
}
for (auto u : g[v]) {
if (u != p) {
auto x = dfs2(u, v);
ckmn(v, mn1[u]);
ckmn(v, mn2[u]);
if (cur.size() < x.size()) {
cur.swap(x);
}
for (const auto &ci : x) {
upd(ci[2]);
cur.insert(ci);
}
}
}
if (depth[v] > mn2[v].first) {
assert(mn1[v].second != mn2[v].second);
ckans(mn1[v].second, mn2[v].second, depth[v] - mn2[v].first);
}
return cur;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#endif
int n, q;
cin >> n >> q;
g.resize(n);
for (int i = 1; i < n; ++i) {
int p;
cin >> p;
--p;
// cout << p + 1 << " " << i + 1 << "\n";
g[i].push_back(p);
g[p].push_back(i);
}
tin.resize(n);
tout.resize(n);
depth.resize(n);
up.resize(k, vector<int>(n));
dfs1(0, -1);
paths.resize(q);
p1.resize(n);
p2.resize(n);
for (int i = 0; i < q; ++i) {
int u, v;
cin >> u >> v;
--u;
--v;
if (depth[u] < depth[v]) {
swap(u, v);
}
if (is_anc(v, u)) {
p2[u].push_back(i);
paths[i] = {u, v, LCA(u, v)};
} else {
if (tin[v] < tin[u]) {
swap(u, v);
}
paths[i] = {u, v, LCA(u, v)};
p1[u].push_back(i);
p2[u].push_back(i);
p2[v].push_back(i);
}
}
mn1.resize(n, {INF, -1});
mn2.resize(n, {INF, -1});
dfs2(0, -1);
if (ans == -1) {
cout << "0\n1 2\n";
} else {
cout << ans << "\n";
// cout << paths[ansi][0] + 1 << " " << paths[ansi][1] + 1 << "\n";
// cout << paths[ansj][0] + 1 << " " << paths[ansj][1] + 1 << "\n";
cout << ansi + 1 << " " << ansj + 1 << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
212 KB |
Checker failed - contact admins or jury |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
212 KB |
Checker failed - contact admins or jury |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
212 KB |
Checker failed - contact admins or jury |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
212 KB |
Checker failed - contact admins or jury |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
273 ms |
28380 KB |
Checker failed - contact admins or jury |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
109 ms |
23260 KB |
Checker failed - contact admins or jury |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
212 KB |
Checker failed - contact admins or jury |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
212 KB |
Checker failed - contact admins or jury |
| 2 |
Halted |
0 ms |
0 KB |
- |
