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:

// default code for competitive programming
// ver 3.141 {{{

// Includes
#include <bits/stdc++.h>

// Defines
#define NAME(x) #x
#define SZ(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()
#define FOR(i, e) for( int i = 0 ; i < (e) ; i++ )
#define ITER(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define REP(i, s, e) for(int i = (s); i <= (e); i++)
#define REPD(i, s, e) for(int i = (s); i >= (e); i--)
#define IOS ios_base::sync_with_stdio( 0 )
#define DEBUG 1
#define fst first
#define snd second
#ifdef ONLINE_JUDGE
#define FILE( fn ) \
    freopen(fn".in","r",stdin); \
    freopen(fn".out","w",stdout);
#else
#define FILE( fn )
#endif

#ifdef AKAI
#define debug( ... ) fprintf( stderr , __VA_ARGS__ )
#else
#define debug( ... )
#endif

using namespace std;

// Typedefs
typedef double real;
typedef long long ll;
typedef pair<ll, int> pli;
typedef tuple<ll, int> tli;
typedef pair<int, int> pii;
typedef tuple<int, int> tii;
typedef unsigned long long ull;

// Some common const.
const double EPS = -1e8;
const double Pi = acos(-1);

// Equal for double
bool inline equ(double a, double b)
{return fabs(a - b) < EPS;}

void RI() {}

template< typename... T >
void RI( int& x , T&... tail )
{
  assert( scanf( "%d" , &x ) == 1 );
  RI( tail... );
}

template< typename Iter , typename F >
inline void out( Iter s , Iter e , F of )
{
  bool flag = 0;
  for( Iter it = s ; it != e ; it++ )
  {
    if( flag ) printf( " " );
    else flag = 1;
    of( *it );
  }
  puts( "" );
}

// }}}
// start ~~QAQ~~

const int MAXN = 100010;
const int LOG  = 22;

struct DominatorTree{
  int n , m , s;
  vector< int > g[ MAXN ] , pred[ MAXN ];
  vector< int > cov[ MAXN ];
  int dfn[ MAXN ] , nfd[ MAXN ] , ts;
  int par[ MAXN ];
  int sdom[ MAXN ] , idom[ MAXN ];

  int mom[ MAXN ] , mn[ MAXN ];

  inline bool cmp( int u , int v )
  { return dfn[ u ] < dfn[ v ]; }

  inline void link( int u , int v )
  { mom[ v ] = u; }

  int eval( int u ){
    if( mom[ u ] == u ) return u;
    int res = eval( mom[ u ] );
    if( cmp( sdom[ mn[ mom[ u ] ] ] , sdom[ mn[ u ] ] ) )
      mn[ u ] = mn[ mom[ u ] ];
    return mom[ u ] = res;
  }

  void init( int _n , int _m , int _s ){
    ts = 0;
    n = _n;
    m = _m;
    s = _s;
    REP( i , 1 , n ) g[ i ].clear() , pred[ i ].clear();
  }
  void addEdge( int u , int v ){
    g[ u ].push_back( v );
    pred[ v ].push_back( u );
  }
  void dfs( int u ){
    ts++;
    dfn[ u ] = ts;
    nfd[ ts ] = u;
    for( int v : g[ u ] ) if( dfn[ v ] == 0 ){
      par[ v ] = u;
      dfs( v );
    }
  }
  void build(){
    REP( i , 1 , n ){
      dfn[ i ] = nfd[ i ] = 0;
      cov[ i ].clear();
      mom[ i ] = mn[ i ] = sdom[ i ] = i;
    }
    dfs( s );
    REPD( i , n , 2 ){
      int u = nfd[ i ];
      for( int v : pred[ u ] ){
        assert( dfn[ v ] != 0 );
        eval( v );
        if( cmp( sdom[ mn[ v ] ] , sdom[ u ] ) )
          sdom[ u ] = sdom[ mn[ v ] ];
      }
      cov[ sdom[ u ] ].push_back( u );
      mom[ u ] = par[ u ];
      for( int w : cov[ par[ u ] ] )
      {
        eval( w );
        if( cmp( sdom[ mn[ w ] ] , par[ u ] ) ) idom[ w ] = mn[ w ];
        else idom[ w ] = par[ u ];
      }
      cov[ par[ u ] ].clear();
    }
    REP( i , 2 , n ){
      int u = nfd[ i ];
      if( idom[ u ] != sdom[ u ] ) idom[ u ] = idom[ idom[ u ] ];
    }
  }
} domT;

int n , m;
int c[ MAXN ];
int dp[ MAXN ];
int dep[ MAXN ];
vector< int > ch[ MAXN ];
int mom[ MAXN ][ LOG ];

void dfs( int u )
{
  for( int v : ch[ u ] )
  {
    dep[ v ] = dep[ u ] + 1;
    dp[ v ] = min( c[ v ] , dp[ u ] );
    dfs( v );
  }
}

inline int lca( int u , int v )
{
  if( dep[ u ] > dep[ v ] ) swap( u , v );
  int diff = dep[ v ] - dep[ u ];
  FOR( i , LOG ) if( diff & ( 1 << i ) )
    v = mom[ v ][ i ];
  if( u == v ) return u;
  REPD( i , LOG-1 , 0 )
    if( mom[ u ][ i ] != mom[ v ][ i ] )
    {
      u = mom[ u ][ i ];
      v = mom[ v ][ i ];
    }
  return mom[ u ][ 0 ];
}

int w[ MAXN ];

int main()
{
  RI( n , m );
  domT.init( n , m , 1 );
  FOR( i , m )
  {
    int u , v;
    RI( u , v );
    domT.addEdge( u , v );
  }
  domT.build();

  REP( i , 1 , n ) RI( c[ i ] );
  REP( i , 1 , n )
  {
    mom[ i ][ 0 ] = domT.idom[ i ];
    ch[ mom[ i ][ 0 ] ].push_back( i );
  }
  REP( j , 1 , LOG-1 ) REP( i , 1 , n )
    mom[ i ][ j ] = mom[ mom[ i ][ j-1 ] ][ j-1 ];

  dp[ 1 ] = c[ 1 ];
  dfs( 1 );

  int q;RI( q );while( q-- )
  {
    int k;RI( k );
    REP( i , 1 , k ) RI( w[ i ] );
    int anc = w[ 1 ];
    REP( i , 2 , k )
      anc = lca( anc , w[ i ] );
    assert( 1 <= anc );
    printf( "%d\n" , dp[ anc ] );
    //int ans = c[ anc ];
    //while( anc )
    //{
      //ans = min( ans , c[ anc ] );
      //anc = mom[ anc ][ 0 ];
    //}
    //printf( "%d\n" , ans );
  }
}