f50fbbf6fe 2022-04-05        kinaba: //-------------------------------------------------------------
f50fbbf6fe 2022-04-05        kinaba: // The Least Common Ancestor
f50fbbf6fe 2022-04-05        kinaba: //
f50fbbf6fe 2022-04-05        kinaba: // Verified by
f50fbbf6fe 2022-04-05        kinaba: //   - ICPC 2021 Yokohama Regional I
f50fbbf6fe 2022-04-05        kinaba: //-------------------------------------------------------------
f50fbbf6fe 2022-04-05        kinaba: 
f50fbbf6fe 2022-04-05        kinaba: 
f50fbbf6fe 2022-04-05        kinaba: template<int K=17>
f50fbbf6fe 2022-04-05        kinaba: struct Lca
f50fbbf6fe 2022-04-05        kinaba: {
f50fbbf6fe 2022-04-05        kinaba: 	const int N;
f50fbbf6fe 2022-04-05        kinaba: 	const vector<int>& depth;
f50fbbf6fe 2022-04-05        kinaba: 	vector<vector<int>> jump;
f50fbbf6fe 2022-04-05        kinaba: 	Lca(int N, const vector<int>& parent, const vector<int>& depth)
f50fbbf6fe 2022-04-05        kinaba: 		: N(N), depth(depth), jump(K, vector<int>(N, -1))
f50fbbf6fe 2022-04-05        kinaba: 	{
f50fbbf6fe 2022-04-05        kinaba: 		jump[0] = parent;
f50fbbf6fe 2022-04-05        kinaba: 		for(int k=0; k+1<K; ++k)
f50fbbf6fe 2022-04-05        kinaba: 		for(int v=0; v<N; ++v)
f50fbbf6fe 2022-04-05        kinaba: 			if(jump[k][v] != -1)
f50fbbf6fe 2022-04-05        kinaba: 				jump[k+1][v] = jump[k][jump[k][v]];
f50fbbf6fe 2022-04-05        kinaba: 	}
f50fbbf6fe 2022-04-05        kinaba: 
f50fbbf6fe 2022-04-05        kinaba: 	int operator()(int a, int b) const {
f50fbbf6fe 2022-04-05        kinaba: 		if(depth[a]>depth[b]) swap(a,b);
f50fbbf6fe 2022-04-05        kinaba: 		for(int k=0; k<K; ++k)
f50fbbf6fe 2022-04-05        kinaba: 			if((depth[b]-depth[a]) & (1<<k))
f50fbbf6fe 2022-04-05        kinaba: 				b = jump[k][b];
f50fbbf6fe 2022-04-05        kinaba: 		if(a == b)
f50fbbf6fe 2022-04-05        kinaba: 			return a;
f50fbbf6fe 2022-04-05        kinaba: 		for(int k=K-1; k>=0; --k)
f50fbbf6fe 2022-04-05        kinaba: 			if(jump[k][a] != jump[k][b]) {
f50fbbf6fe 2022-04-05        kinaba: 				a = jump[k][a];
f50fbbf6fe 2022-04-05        kinaba: 				b = jump[k][b];
f50fbbf6fe 2022-04-05        kinaba: 			}
f50fbbf6fe 2022-04-05        kinaba: 		return jump[0][a];
f50fbbf6fe 2022-04-05        kinaba: 	}
f50fbbf6fe 2022-04-05        kinaba: };