Untitled

mail@pastecode.io avatar
unknown
plain_text
18 days ago
1.5 kB
2
Indexable
Never
#include <bits/stdc++.h>

const int N = 2e5+5;
const int inf = 1e9;

using namespace std;

vector<int> g[N] , v;
int B = 500;
int up[N][20] , dep[N] , ans[N];
queue<int> q;


int lca(int a , int b){
	if(dep[b] < dep[a]) swap(a , b);
	for(int i = 19; i >= 0;){
		if(dep[up[b][i]] >= dep[a]) b = up[b][i];
		else i--;
	}
	if(a == b){
		return dep[a];
	}
	for(int i = 19; i >= 0;){
		if(up[b][i] != up[a][i]){
			b = up[b][i];
			a = up[a][i];
		}
		else i--;
	}
	return dep[up[a][0]];
}

void dfs(int v = 1 , int p = 0){
	up[v][0] = p;
	for(int i = 1; i < 20; i++){
		up[v][i] = up[up[v][i-1]][i-1];
	}
	dep[v] = dep[p]+1;
	for(auto to : g[v]){
		if(to == p) continue;
		dfs(to , v);
	}
}

void bfs(int v){
	for(auto to : g[v]){
		if(ans[to] > ans[v]+1){
			ans[to] = ans[v]+1;
			q.push(to);
		}
	}
}

void solve(){
	int n , m;
	cin >> n >> m;
	for(int i = 2; i <= n; i++){
		int a;
		cin >> a;
		g[a].push_back(i);
		g[i].push_back(a);
	}
	dfs();
	for(int i = 1; i <= n; i++) ans[i] = inf;
	while(m--){
		int t , x;
		cin >> t >> x;
		if(t == 1) v.push_back(x) , ans[x] = 0;
		else {
			int mn = ans[x];
			for(auto it : v) mn = min(dep[it] + dep[x] - lca(it , x)*2 , mn);
			if(mn == inf) mn = -1;
			cout << mn <<"\n";
		}
		if(v.size() == B){
			for(auto it : v) q.push(it);
			while(!q.empty()){
				bfs(q.front());
				q.pop();
			}
			v.clear();
		} 
	}
}
signed main(){
	solve();
	return 0;
}
Leave a Comment