#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
//#define int long long
typedef pair<int,int>PII;
const int N = 3e6 + 5,MOD = 1e9 + 7,INF = 1e9;
struct node{
int l,r;
}tr[N];
vector<array<int,2>>G[N];
int root[2],tot;
int n, m;
void build(int &u,int l,int r,int flag) {
if (l == r) {
u = l;
return;
}
if (!u) u = ++tot;
//cout << flag << " " << u << " " << l << " " << r << endl;
int mid = l + r >> 1;
build(tr[u].l, l, mid, flag);
build(tr[u].r, mid + 1, r, flag);
if (!flag) G[u].push_back({tr[u].l, 0}), G[u].push_back({tr[u].r, 0});
else G[tr[u].l].push_back({u, 0}), G[tr[u].r].push_back({u, 0});
}
void add_edge(int l,int r,int x,int y,int u,int v,int flag,int w) {
if (x <= l && r <= y) {
//cout << u << " " << l << " " << r << " " << v << endl;
if (!flag) G[v].push_back({u, w});
else G[u].push_back({v, w});
return;
}
int mid = l + r >> 1;
if (x <= mid) add_edge(l, mid, x, y, tr[u].l, v, flag, w);
if (y > mid) add_edge(mid + 1, r, x, y, tr[u].r, v, flag, w);
}
int d[N],f[N];
vector<int>Tree[N];
int siz[N],fa[N],son[N],dep[N];
int id[N],cnt,top[N];
void dijk(int s) {
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,s});
for (int i = 1; i <= tot; i++) d[i] = INF;
d[s] = 0;
while (!q.empty()) {
auto [dt,u] = q.top();
q.pop();
if(f[u]) continue;
f[u] = 1;
for (auto [v, w]: G[u]) {
//cout << u << " " << v << endl;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push({d[v],v});
}
}
}
for(int i = 2; i <= n; i++ ){
if(d[id[i]] == INF) cout << -1 ;
else cout << d[id[i]];
cout << " ";
}
}
void dfs1(int u,int fat,int deps) {
fa[u] = fat, dep[u] = deps, siz[u] = 1;
for (auto v: Tree[u]) {
if (v == fat) continue;
dfs1(v, u, deps + 1);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u,int t) {
id[u] = ++cnt, top[u] = t;
//cout << u << " " << id[u] << endl;
if (!son[u]) return;
dfs2(son[u], t);
for (auto v: Tree[u]) {
if (v == son[u] || v == fa[u]) continue;
dfs2(v, v);
}
}
void add_path(int u,int v,int x,int y){
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) swap(u,v);
add_edge(1,n,id[top[u]],id[u],root[0],id[x],0,1);
add_edge(1,n,id[top[u]],id[u],root[0],id[y],0,1);
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u,v);
add_edge(1,n,id[v],id[u],root[0],id[x],0,1);
add_edge(1,n,id[v],id[u],root[0],id[y],0,1);
}
void solve() {
cin >> n >> m;
tot = n;
build(root[0], 1, n, 0);
for (int i = 2, u; i <= n; i++) {
cin >> u;
Tree[u].push_back(i);
Tree[i].push_back(u);
}
dfs1(1, 0, 0);
dfs2(1, 1);
while (m--) {
int u, v;
cin >> u >> v;
add_path(u, v, u, v);
}
dijk(1);
}
signed main() {
IOS;
int T = 1;
//cin >> T;
while (T--) {
solve();
}
}
杀鸡用牛刀了
没学过线段树建图,写着玩玩,下回试试多校那道网络流