/**
* Author: Sergey Kopeliovich (
[email protected])
*
* O(m^2logn + nlogn)
* Насчитали за O(nlogn) двоичные подъёмы для LCA.
* Для каждой пары путей ищем пересечение за O(1).
*/
#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--)
const int N = 1e5, K = 17;
int n, k, p[N][K], a[N], b[N], lca[N], dep[N];
void up( int &a, int k ) {
fornd(i, K)
if (k >= (1 << i))
a = p[a][i], k -= 1 << i;
}
int getLcaDepth( int a, int b ) {
up(a, dep[a] - dep[b]);
up(b, dep[b] - dep[a]);
fornd(i, K)
if (p[a][i] != p[b][i])
a = p[a][i], b = p[b][i];
return dep[a == b ? a : p[a][0]];
}
int main() {
scanf("%d%d", &n, &k);
assert(n <= N && k <= N);
p[0][0] = 0;
for (int i = 1; i < n; i++) {
scanf("%d", &p[i][0]);
dep[i] = dep[--p[i][0]] + 1;
}
forn(k, K - 1)
forn(i, n)
p[i][k + 1] = p[p[i][k]][k];
int ma = 0, ri = 0, rj = 1;
forn(i, k) {
scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
lca[i] = getLcaDepth(a[i], b[i]);
forn(j, i) {
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;
}
}
printf("%d\n", ma);
printf("%d %d\n", ri + 1, rj + 1);
}
Compilation message (stderr)
sending.cpp: In function 'int main()':
sending.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
39 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
43 | scanf("%d", &p[i][0]);
| ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
52 | scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~