#include <cstdio> #include <iostream> #include <vector> #include <utility> #include <cstring> #include <algorithm> const int maxN = 100010; int n, tcs, k; int currDepth; long long sol; int parent[ maxN ]; /// parent u cdekomp stablu int depth[ maxN ]; /// dubina u cdekomp stablu int subSize[ maxN ]; /// pomocni array u dfsu bool bio[ maxN ]; bool inDecomp[ maxN ]; long long dist[ 20 ][ maxN ]; /// udaljenost jota od parenta na dubini i std::vector< std::pair< int, int > > PS[ maxN ]; std::vector< int > currComp; std::vector< int > children[ maxN ]; std::vector< int > dNodes[ 20 ]; std::vector< int > subset; void dfs( int x ) { bio[ x ] = true; int currSub = 0; currComp.push_back( x ); for( int i = 0; i < PS[ x ].size(); ++i ) { int currNeigh = PS[ x ][ i ].first; if( !bio[ currNeigh ] && !inDecomp[ currNeigh ] ) { /// pripada komponenti koju trenutno pretrazujemo dfs( currNeigh ); currSub += subSize[ currNeigh ]; } } subSize[ x ] = currSub + 1; /// velicine moje djece plus ja bio[ x ] = false; return; } void dfs2( int x, int d ) { bio[ x ] = true; dist[ currDepth ][ x ] = d; for( int i = 0; i < PS[ x ].size(); ++i ) { int currNeigh = PS[ x ][ i ].first; if( !bio[ currNeigh ] ) { dfs2( currNeigh, d + PS[ x ][ i ].second ); } } bio[ x ] = false; } int decompose( int x ) { /// potkomponenta u kojoj je ovaj cvor obidi i nadi centralni cvor currComp.clear(); dfs( x ); /// u DFSu izracunaj velicinu podstabla, root je u x-u int compSize = currComp.size(); for( int i = 0; i < compSize; ++i ) { /// u potrazi za savrsenim kandidatom int currCompMem = currComp[ i ]; /// potencijalni kandidat int maxChild = 0; for( int j = 0; j < PS[ currCompMem ].size(); ++j ) { int currNeigh = PS[ currCompMem ][ j ].first; if( inDecomp[ currNeigh ] || subSize[ currNeigh ] > subSize[ currCompMem ] ) { /// ne zelim susjede koji su /// vec u kompoziciji ili su mi bili parent u DFSu, znaci gledam samo djecu continue; } maxChild = std::max( maxChild, subSize[ currNeigh ] ); } if( std::max( maxChild, compSize-subSize[ currCompMem ] ) <= compSize/2 ) { /// savrseni kandidat pronaden inDecomp[ currCompMem ] = true; for( int j = 0; j < compSize; ++j ) { subSize[ currComp[ j ] ] = 0; } for( int j = 0; j < PS[ currCompMem ].size(); ++j ) { int currNeigh = PS[ currCompMem ][ j ].first; if( !inDecomp[ currNeigh ] ) { int ch = decompose( currNeigh ); parent[ ch ] = currCompMem; } } return currCompMem; } } return 0; /// resetiraj subSize } void calcDepth( int x ) { if( parent[ x ] == -1 ) { depth[ x ] = 0; return; } if( depth[ parent[ x ] ] == -1 ) { calcDepth( parent[ x ] ); } depth[ x ] = depth[ parent[ x ] ] + 1; return; } int main () { std::memset( bio, 0, sizeof bio ); std::memset( inDecomp, 0, sizeof inDecomp ); scanf( "%d%d", &n, &tcs ); for( int i = 0; i < n-1; ++i ) { int a, b, c; scanf( "%d%d%d", &a, &b, &c ); --a; --b; PS[ a ].push_back( std::make_pair( b, c ) ); PS[ b ].push_back( std::make_pair( a, c ) ); } int root = decompose( 0 ); parent[ root ] = -1; std::memset( depth, -1, sizeof depth ); /// 2 for( int i = 0; i < n; ++i ) { calcDepth( i ); } // for( int i = 0; i < n; ++i ) { // printf( "i:%d depth:%d parent:%d\n", i, depth[ i ], parent[ i ] ); // } /// 1 - children dio for( int i = 0; i < n; ++i ) { if( parent[ i ] != -1 ) { int par = parent[ i ]; children[ par ].push_back( i ); } } /// 2.5 for( int i = 0; i < n; ++i ) { dNodes[ depth[ i ] ].push_back( i ); } /// 3 std::memset( bio, 0, sizeof bio ); for( int i = 0; i < 20; ++i ) { currDepth = i; for( int j = 0; j < dNodes[ i ].size(); ++j ) { dfs2( dNodes[ i ][ j ], 0 ); bio[ dNodes[ i ][ j ] ] = true; } } // for( int i = 0; i < n; ++i ) { // for( int j = 0; j < 4; ++j ) { // printf( "dist[ %d ][ %d ] = %d\n", j, i, dist[ j ][ i ] ); // } // } std::memset( subSize, 0, sizeof subSize ); while( tcs-- ) { /// 4.1 subset.clear(); sol = 0; scanf( "%d", &k ); for( int i = 0; i < k; ++i ) { int temp; scanf( "%d", &temp ); --temp; subset.push_back( temp ); } for( int i = 0; i < k; ++i ) { int curr = subset[ i ]; while( curr != -1 ) { ++subSize[ curr ]; curr = parent[ curr ]; } } /// 4.2 for( int i = 0; i < k; ++i ) { int akt = subset[ i ]; int curr = subset[ i ]; int cDepth = depth[ curr ]; while( cDepth > 0 ) { sol += dist[ cDepth-1 ][ akt ] * (subSize[ parent[ curr ] ] - subSize[ curr ]); curr = parent[ curr ]; --cDepth; } } /// 4.1 for( int i = 0; i < k; ++i ) { int curr = subset[ i ]; while( curr != -1 ) { --subSize[ curr ]; curr = parent[ curr ]; } } std::cout << sol << std::endl; } return 0; }