| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 291905 | Diuven | ROI16_sending (ROI16_sending) | C++17 | 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.
#include <cassert>
#include <cstdio>
#include <set>
#include <vector>
#define mp make_pair
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define data __data
using namespace std;
const int L = 19;
const int N = (int) 2e5 + 10;
int n, m, curt, u, v, opt = 0, opti = 0, optj = 1, h[N], firstoc[N], order[2 * N], p[2 * N][L], mx[2 * N], curpos;
vector<int> adj[N];
typedef pair<int, int> tpath;
vector<tpath> paths[N], die[N];
struct cmp {
bool operator()(tpath a, tpath b) {
return (mp(firstoc[a.fs], a.sc) < mp(firstoc[b.fs], b.sc));
}
};
typedef set< tpath, cmp > tpathset;
tpathset data[N];
void dfs(int v, int pv = -1) {
firstoc[v] = curpos;
order[curpos++] = v;
for (int u : adj[v]) {
if (u != pv) {
h[u] += h[v];
dfs(u, v);
order[curpos++] = v;
}
}
}
int plusik(int a, int b) {
return (h[a] < h[b]) ? a : b;
}
int lca(int u, int v) {
u = firstoc[u], v = firstoc[v];
if (u > v) {
swap(u, v);
}
int k = mx[v - u + 1];
return plusik(p[u][k], p[v - (1 << k) + 1][k]);
}
void relax(int v, tpath path1, tpath path2) {
int res = h[v] - h[lca(v, path1.fs)] - h[lca(v, path2.fs)] + h[lca(path1.fs, path2.fs)];
if (res > opt) {
opt = res, opti = path1.sc, optj = path2.sc;
}
}
void add(int v, tpath path) {
auto match = data[v].lower_bound(path);
if (match != data[v].end()) {
relax(v, path, *match);
}
if (match != data[v].begin()) {
relax(v, path, *(--match));
}
data[v].insert(path);
}
void solve(int v, int pv = -1) {
for (int u : adj[v]) {
if (u != pv) {
solve(u, v);
if (sz(data[v]) < sz(data[u])) {
data[v].swap(data[u]);
}
for (tpath path : data[u]) {
add(v, path);
}
}
}
for (tpath path : paths[v]) {
add(v, path);
}
for (tpath path : die[v]) {
data[v].erase(path);
}
}
int main() {
freopen("twopaths.in", "r", stdin);
freopen("twopaths.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++i) {
scanf("%d", &u), --u;
adj[u].pb(i), adj[i].pb(u);
}
for (int i = 1; i < n; ++i)
h[i] = 1;
dfs(0, -1);
mx[1] = 0;
for (int i = 2; i < curpos; ++i) {
mx[i] = mx[i - 1];
if (i == (1 << (mx[i] + 1))) {
mx[i]++;
}
}
for (int i = 0; i < curpos; ++i)
p[i][0] = order[i];
for (int j = 1; j < L; ++j)
for (int i = 0; i + (1 << j) <= curpos; ++i) {
p[i][j] = plusik(p[i][j - 1], p[i + (1 << (j - 1))][j - 1]);
}
for (int i = 0; i < m; ++i) {
scanf("%d%d", &u, &v), --u, --v;
paths[u].pb(mp(v, i)), paths[v].pb(mp(u, i));
int w = lca(u, v);
die[w].pb(mp(v, i)), die[w].pb(mp(u, i));
}
solve(0, -1);
printf("%d\n%d %d\n", opt, opti + 1, optj + 1);
return 0;
}