#include <stdio.h>
#include <stdlib.h>
#define N 200000
#define M 200000
#define L 19 /* L = ceil(log2(M * 2)) */
#define M_ (1 << L)
#define N_ (M_ * (L + 1) + 1)
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *ej[N], eo[N], *eh[N], eo_[N];
void append(int **ej, int *eo, int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int dd[N], pp[N], qq[N], ta[N], tb[N];
int dfs1(int i, int d) {
int o, s, k_, j_;
dd[i] = d;
s = 1, k_ = 0, j_ = -1;
for (o = eo[i]; o--; ) {
int j = ej[i][o], k = dfs1(j, d + 1);
s += k;
if (k_ < k)
k_ = k, j_ = j;
}
qq[i] = j_;
return s;
}
void dfs2(int i, int q) {
static int time;
int o, j_;
ta[i] = time++;
j_ = qq[i], qq[i] = q;
if (j_ != -1)
dfs2(j_, q);
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != j_)
dfs2(j, j);
}
tb[i] = time;
}
int lca(int i, int j) {
while (qq[i] != qq[j])
if (dd[qq[i]] > dd[qq[j]])
i = pp[qq[i]];
else
j = pp[qq[j]];
return dd[i] < dd[j] ? i : j;
}
int ii[M * 2], idx[M * 2];
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ta[ii[hh[j]]] - ta[ii[h]];
if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}
int hh_[M_], dd1[M_ * 2], ddmn[M_ * 2], m_;
void build(int l, int r) {
int m;
if (r - l == 1)
ddmn[l + r] = INF;
else {
m = (l + r) / 2;
build(l, m), build(m, r);
ddmn[l + r] = min(min(ddmn[l + m], dd1[m]), ddmn[m + r]);
}
}
int ll[N_], rr[N_], ddp[N_], ddq[N_], ddmx[N_];
int node(int l, int r, int i) {
static int _ = 1;
int t = _++;
if (r - l == 1)
ddp[t] = ddq[t] = INF, ddmx[t] = -1;
else {
int m = (l + r) / 2;
if (i < m) {
ll[t] = node(l, m, i);
ddp[t] = ddp[ll[t]], ddq[t] = min(min(ddq[ll[t]], dd1[m]), ddmn[m + r]);
} else {
rr[t] = node(m, r, i);
ddp[t] = min(min(ddmn[l + m], dd1[m]), ddp[rr[t]]), ddq[t] = ddq[rr[t]];
}
ddmx[t] = -1;
}
return t;
}
int remove_(int t, int l, int r, int i) {
int m;
if (r - l == 1)
t = 0;
else {
m = (l + r) / 2;
if (i < m)
ll[t] = remove_(ll[t], l, m, i);
else
rr[t] = remove_(rr[t], m, r, i);
if (ll[t] == 0 && rr[t] == 0)
t = 0;
else {
ddp[t] = ll[t] ? ddp[ll[t]] : min(min(ddmn[l + m], dd1[m]), ddp[rr[t]]);
ddq[t] = rr[t] ? ddq[rr[t]] : min(min(ddq[ll[t]], dd1[m]), ddmn[m + r]);
ddmx[t] = max(max(ddmx[ll[t]], ddmx[rr[t]]), min(min(ddq[ll[t]], dd1[m]), ddp[rr[t]]));
}
}
return t;
}
int merge(int t1, int t2, int l, int r) {
int m;
if (t1 == 0)
return t2;
if (t2 == 0)
return t1;
m = (l + r) / 2;
ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r);
ddp[t1] = ll[t1] ? ddp[ll[t1]] : min(min(ddmn[l + m], dd1[m]), ddp[rr[t1]]);
ddq[t1] = rr[t1] ? ddq[rr[t1]] : min(min(ddq[ll[t1]], dd1[m]), ddmn[m + r]);
ddmx[t1] = max(max(ddmx[ll[t1]], ddmx[rr[t1]]), min(min(ddq[ll[t1]], dd1[m]), ddp[rr[t1]]));
return t1;
}
int find_p(int t, int l, int r) {
int m;
if (r - l == 1)
return hh_[l] >> 1;
m = (l + r) / 2;
return ll[t] ? find_p(ll[t], l, m) : find_p(rr[t], m, r);
}
int find_q(int t, int l, int r) {
int m;
if (r - l == 1)
return hh_[l] >> 1;
m = (l + r) / 2;
return rr[t] ? find_q(rr[t], m, r) : find_q(ll[t], l, m);
}
void find_mx(int t, int l, int r, int *h1, int *h2) {
int m;
m = (l + r) / 2;
if (ddmx[ll[t]] == ddmx[t])
find_mx(ll[t], l, m, h1, h2);
else if (ddmx[rr[t]] == ddmx[t])
find_mx(rr[t], m, r, h1, h2);
else
*h1 = find_q(ll[t], l, m), *h2 = find_p(rr[t], m, r);
}
int t_, d_, h1_, h2_;
void dfs3(int i) {
static int hh[M * 2], tt[M * 2], dd1[M * 2];
int m, cnt, h, o, d, d1;
if (eo_[i]) {
m = 0;
for (o = eo_[i]; o--; ) {
h = eh[i][o];
hh[m++] = h << 1 | 0, hh[m++] = h << 1 | 1;
}
sort(hh, 0, m);
cnt = 0;
for (h = 0; h <= m; h++) {
d1 = h == 0 || h == m ? -1 : dd[lca(ii[hh[h]], ii[hh[h - 1]])];
while (cnt >= 2 && dd1[cnt - 1] >= d1) {
tt[cnt - 2] = merge(tt[cnt - 2], tt[cnt - 1], 0, m_);
if (ddmx[tt[cnt - 2]] != -1) {
d = dd1[cnt - 1] + ddmx[tt[cnt - 2]] - dd[i] * 2;
if (d_ < d)
d_ = d, find_mx(tt[cnt - 2], 0, m_, &h1_, &h2_);
}
cnt--;
}
if (h < m)
tt[cnt] = node(0, m_, idx[hh[h] ^ 1]), dd1[cnt] = d1, cnt++;
}
t_ = merge(t_, tt[0], 0, m_);
}
if (ddmx[t_] != -1) {
d = ddmx[t_] - dd[i];
if (d_ < d)
d_ = d, find_mx(t_, 0, m_, &h1_, &h2_);
}
for (o = eo[i]; o--; ) {
int j = ej[i][o];
dfs3(j);
}
for (o = eo_[i]; o--; ) {
h = eh[i][o];
t_ = remove_(t_, 0, m_, idx[h << 1 | 0]);
t_ = remove_(t_, 0, m_, idx[h << 1 | 1]);
}
}
int main() {
int n, m, h, i, j;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 1; i < n; i++) {
scanf("%d", &pp[i]), pp[i]--;
append(ej, eo, pp[i], i);
}
dfs1(0, 0);
dfs2(0, 0);
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (h = 0; h < m; h++) {
scanf("%d%d", &i, &j), i--, j--;
ii[h << 1 | 0] = i, ii[h << 1 | 1] = j;
append(eh, eo_, lca(i, j), h);
}
for (h = 0; h < m * 2; h++)
hh_[h] = h;
sort(hh_, 0, m * 2);
for (h = 0; h < m * 2; h++)
idx[hh_[h]] = h;
for (h = 1; h < m * 2; h++)
dd1[h] = dd[lca(ii[hh_[h - 1]], ii[hh_[h]])];
m_ = 1;
while (m_ < m * 2)
m_ <<= 1;
build(0, m_);
ddp[0] = -1, ddq[0] = -1, ddmx[0] = -1;
d_ = 0, h1_ = 0, h2_ = 1, dfs3(0);
printf("%d\n", d_);
printf("%d %d (%d %d %d %d)\n", h1_ + 1, h2_ + 1, ii[h1_ << 1 | 0], ii[h1_ << 1 | 1], ii[h2_ << 1 | 0], ii[h2_ << 1 | 1]);
return 0;
}
Compilation message
sending.c: In function 'append':
sending.c:25:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
25 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
sending.c: In function 'main':
sending.c:252:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
252 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
sending.c:256:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
256 | scanf("%d", &pp[i]), pp[i]--;
| ^~~~~~~~~~~~~~~~~~~
sending.c:264:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
264 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31068 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31068 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31068 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31068 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
69716 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
69460 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31068 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31068 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
