/**
* 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);
}
Compilation message
sending.cpp:27:1: error: 'vector' does not name a type
27 | vector<int> ids[N], c[N];
| ^~~~~~
sending.cpp: In function 'void mark(int, int)':
sending.cpp:32:2: error: 'ids' was not declared in this scope
32 | ids[v].pb(i);
| ^~~
sending.cpp: In function 'void dfs(int, int, int)':
sending.cpp:37:15: error: 'c' was not declared in this scope
37 | for (int x : c[v])
| ^
sending.cpp: In function 'int main()':
sending.cpp:71:3: error: 'c' was not declared in this scope
71 | c[i].pb(p[i]), c[p[i]].pb(i);
| ^
sending.cpp:94:2: error: 'vector' was not declared in this scope
94 | vector<pii> et;
| ^~~~~~
sending.cpp:13:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
12 | #include <algorithm>
+++ |+#include <vector>
13 |
sending.cpp:94:12: error: expected primary-expression before '>' token
94 | vector<pii> et;
| ^
sending.cpp:94:14: error: 'et' was not declared in this scope
94 | vector<pii> et;
| ^~
sending.cpp:97:16: error: 'ids' was not declared in this scope
97 | for (int x : ids[v]) {
| ^~~
sending.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
70 | scanf("%d", &p[i]), p[i]--;
| ~~~~~^~~~~~~~~~~~~
sending.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
