| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 292009 | Diuven | ROI16_sending (ROI16_sending) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* Author: Sergey Kopeliovich ([email protected])
*
* O(nlogn + mhlogn)
* Насчитали за O(nlogn) двоичные подъёмы для LCA.
* Насчитали за O(mh) для каждой вершины дерева список путей, проходящих через неё.
* Фиксируем нижний конец пересечения A. Сортируем концы путей по порядку в Эйлервом Обходе, используя LCA смотрим ответы для соседних.
*/
#include <cassert>
#include <cstdio>
#include <algorithm>
using namespace std;
#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define fornd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define sz(a) (int)(a).size()
#define pb push_back
#define all(a) (a).begin(), (a).end()
typedef pair <int, int> pii;
const int N = 1e5, K = 18;
int n, k, p[N], a[N], b[N], lca[N], dep[N];
vector<int> ids[N], c[N];
int an, pos[N], bn[2 * N];
int sparse[K][2 * N];
inline void mark( int v, int i ) {
ids[v].pb(i);
}
void dfs( int v, int d = 0, int p = -1 ) {
pos[v] = an, dep[v] = sparse[0][an++] = d;
for (int x : c[v])
if (x != p)
dfs(x, d + 1, v), sparse[0][an++] = d;
}
inline int getLcaDepth( int a, int b ) {
a = pos[a], b = pos[b];
if (a > b)
swap(a, b);
int k = bn[++b - a];
assert(k < K);
return min(sparse[k][a], sparse[k][b - (1 << k)]);
}
int ma = 0, ri = 0, rj = 1;
void relax( int i, int j ) {
if (i == j) return;
int M = max(lca[i], lca[j]);
#define F(a, b) max(0, getLcaDepth(a, b) - M)
int sum = F(a[i], a[j]) + F(a[i], b[j]) + F(b[i], a[j]) + F(b[i], b[j]);
if (ma < sum)
ma = sum, ri = i, rj = j;
}
int main() {
#define NAME "twopaths"
assert(freopen(NAME ".in", "r", stdin));
assert(freopen(NAME ".out", "w", stdout));
scanf("%d%d", &n, &k);
assert(n <= N && k <= N);
for (int i = 1; i < n; i++) {
scanf("%d", &p[i]), p[i]--;
c[i].pb(p[i]), c[p[i]].pb(i);
}
dfs(0);
for (int i = 2; i <= an; i++)
bn[i] = bn[i >> 1] + 1;
forn(k, K - 1)
forn(i, an - (1 << k) + 1)
sparse[k + 1][i] = min(sparse[k][i], sparse[k][i + (1 << k)]);
forn(i, k) {
scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
lca[i] = getLcaDepth(a[i], b[i]);
int v = a[i], u = b[i];
while (dep[v] > dep[u])
mark(v, i), v = p[v];
while (dep[u] > dep[v])
mark(u, i), u = p[u];
while (v != u) {
mark(v, i), v = p[v];
mark(u, i), u = p[u];
}
mark(v, i);
}
vector<pii> et;
forn(v, n) {
et.clear();
for (int x : ids[v]) {
et.pb(pii(pos[a[x]], x));
et.pb(pii(pos[b[x]], x));
}
sort(all(et));
forn(i, sz(et) - 1)
relax(et[i].second, et[i + 1].second);
}
printf("%d\n", ma);
printf("%d %d\n", ri + 1, rj + 1);
}