Problem: Example

Input

8 8
1 2
1 3
2 4
2 5
2 8
3 5
3 6
4 7
1000
100
100
10
10
10
1
1
3
2 8 6
2 4 7
2 7 8


Output

1000
10
100

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 50005

int N,M;
int root;
int COST[SIZE],in_num[SIZE],minimum[SIZE];

//支配木
int num_visited;
int vertex[SIZE];
int sdom[SIZE],idom[SIZE];
int dom_parent[SIZE],work[SIZE],uf_parent[SIZE];
vector<int> dom_G[SIZE],dom_rev_G[SIZE],bucket[SIZE];

//LCA
int MAX_LOG_V = 17;
int POW[18];
int parent[18][SIZE];
int depth[SIZE];
vector<int> G[SIZE];

int find(int node_id){
	if(node_id == uf_parent[node_id]){

		return node_id;

	}else{

		int ret = find(uf_parent[node_id]);

		if(sdom[work[node_id]] > sdom[work[uf_parent[node_id]]]){

			work[node_id] = work[uf_parent[node_id]];
		}

		return uf_parent[node_id] = ret;
	}
}

void LINK(int child,int arg_parent){

	uf_parent[child] = arg_parent;
}

void dom_dfs(int node_id,int pre){

	dom_parent[node_id] = pre;
	vertex[num_visited] = node_id;
	sdom[node_id] = num_visited++;

	for(int i = 0; i < dom_G[node_id].size(); i++){

		int next = dom_G[node_id][i];
		if(sdom[next] != -1)continue;

		dom_dfs(next,node_id);
	}
}

int EVAL(int node_id){

	find(node_id);
	return work[node_id];
}



//parentとdepthを再帰的に設定
void dfs(int node_id,int parent_id,int d){
	parent[0][node_id] = parent_id;
	depth[node_id] = d;
	for(int i = 0; i < G[node_id].size(); i++){
		if(G[node_id][i] != parent_id)dfs(G[node_id][i],node_id,d+1);
	}
}

//初期化
void init(){
	//parent[0]とdepthを初期化する
	dfs(root,-1,0);
	//parentを初期化する
	for(int k = 0; k + 1 < MAX_LOG_V; k++){
		for(int node_id = 0; node_id < N; node_id++){
			if(parent[k][node_id] < 0)parent[k+1][node_id] = -1; //node_idの2^k上のノードがルートノードより上なら、2^(k+1)上も同様とする
			else{
				parent[k+1][node_id] = parent[k][parent[k][node_id]];
			}
		}
	}
}

//leftとrightのLCAを求める
int lca(int left,int right){
	//leftとrightの深さが同じになるまで親を辿る
	if(depth[left] > depth[right])swap(left,right); //rightの方が深い所にいる

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(depth[right]-depth[left] >= POW[k]){ //たとえば深さの差が39なら、32+4+2+1のように、ノードを上方に移動させる
			right = parent[k][right];
		}
	}

	if(left == right)return left;

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(parent[k][left] == parent[k][right]){
			//Do nothing
		}else{
			left = parent[k][left];
			right = parent[k][right];
		}
	}
	return parent[0][left]; //最後は、leftの親とrightの親が必ず一致している
}

//idomグラフ上の、自分を含めた先祖の最小コストを求める
void recursive(int node_id){

	for(int i = 0; i < G[node_id].size(); i++){

		int child = G[node_id][i];

		minimum[child] = min(minimum[child],minimum[node_id]);
		recursive(child);
	}
}


int main(){

	scanf("%d %d",&N,&M);

	int from,to;
	for(int loop = 0; loop < M; loop++){

		scanf("%d %d",&from,&to);
		from--;
		to--;
		dom_G[from].push_back(to);
		dom_rev_G[to].push_back(from);
	}

	for(int i = 0; i < N; i++){

		scanf("%d",&COST[i]);
	}

	root = 0;
	num_visited = 0;

	for(int i = 0; i < N; i++){

		sdom[i] = -1; //半支配節
		uf_parent[i] = i; //経路圧縮用配列
		work[i] = i; //仮sdom
	}

	dom_dfs(root,-1);

	for(int i = N-1; i >= 1; i--){

		int node_id = vertex[i];

		for(int k = 0; k < dom_rev_G[node_id].size(); k++){

			int pre_node = dom_rev_G[node_id][k];
			int u = EVAL(pre_node); //分岐の始点を求める
			sdom[node_id] = min(sdom[node_id],sdom[u]);
		}
		bucket[vertex[sdom[node_id]]].push_back(node_id);

		for(int k = 0; k < bucket[dom_parent[node_id]].size(); k++){

			int v = bucket[dom_parent[node_id]][k];
			int u = EVAL(v);

			if(sdom[u] < sdom[v]){

				idom[v] = u;
			}else{

				idom[v] = dom_parent[node_id];
			}
		}
		bucket[dom_parent[node_id]].clear();
		LINK(node_id,dom_parent[node_id]);
	}

	for(int i = 0; i < N; i++){

		in_num[i] = 0;
	}

	for(int i = 1; i < N; i++){

		int w = vertex[i];
		if(idom[w] != vertex[sdom[w]]){

			idom[w] = idom[idom[w]];
		}
		G[idom[w]].push_back(w); //idomの有向グラフを作る
	}

	POW[0] = 1;
	for(int i = 1; i <= 17; i++){

		POW[i] = POW[i-1]*2;
	}

	init();

	minimum[root] = COST[root];
	for(int i = 1;i < N; i++){

		minimum[i] = COST[i];
	}

	recursive(root);

	int num_query;
	scanf("%d",&num_query);

	int tmp;
	int LCA,tmp_node;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d",&tmp);

		scanf("%d",&tmp_node);
		tmp_node--;

		if(tmp == 1){

			printf("%d\n",minimum[tmp_node]);

		}else{

			LCA = tmp_node;
			for(int i = 1; i < tmp; i++){

				scanf("%d",&tmp_node);
				tmp_node--;
				LCA = lca(LCA,tmp_node); //idomグラフ上でのlcaを求める
			}
			printf("%d\n",minimum[LCA]);
		}
	}

	return 0;
}