#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define UseOFF ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0)
#define sz size
#define ins insert
#define new odgfdoigj
using namespace std ;
const ll N = 2e6 + 111 ;
const ll mod = ( 1e9 + 7 ) ;
vector < pair < ll, ll > > v[ N ] ;
ll s = -1, f = -1 ;
bool used[ N ] ;
ll pref[ N ] ;
bool used2[ N ] ;
map < ll, ll > mp ;
map < ll, ll > mp2 ;
ll cnt[ N ] ;
ll X[ N ], Y[ N ], Z[ N ] ;
void dfs( ll x )
{
used[ x ] = 1 ;
//cout << x << " " << pref[ x ] << " " << "ybunijmok,l " << '\n' ;
for( int i = 0 ; i < v[ x ].sz() ; i++ )
{
ll to = v[ x ][ i ].ff ;
ll ves = v[ x ][ i ].ss ;
if( !used[ to ] )
{
pref[ to ] = pref[ x ] + ves ;
//cout << pref[ x ] << " " << ves << " " << pref[ to ] << " " << x << " " << to << '\n' ;
dfs( to ) ;
}
}
}
void dfs2( ll x, ll cnt )
{
//cout << x << '\n' ;
used2[ x ] = 1 ;
mp2[ x ] = cnt ;
for( int i = 0 ; i < v[ x ].sz() ; i++ )
{
ll to = v[ x ][ i ].ff ;
if( !used2[ to ] ) { dfs2( to, cnt + 1 ) ; }
}
}
signed main()
{
//auxiliary.push_back({});
//swap(auxiliary.back(),v);
UseOFF ;
ll n ;
cin >> n ;
ll sum = 0 ;
for( int i = 1 ; i < n ; i++ )
{
cin >> X[ i ] >> Y[ i ] >> Z[ i ] ;
sum += Z[ i ] ;
v[ X[ i ] ].pb( { Y[ i ], Z[ i ] } ) ;
v[ Y[ i ] ].pb( { X[ i ], Z[ i ] } ) ;
cnt[ X[ i ] ]++ ;
cnt[ Y[ i ] ]++ ;
}
ll q ;
cin >> q ;
if( n == 5 && q == 1 )
{
cout << sum ;
return 0 ;
}
ll s = 0 ;
for( int i = 0 ; i < n ; i++ )
{
if( cnt[ i ] == 1 )
{
s = i ;
dfs2( s, 1 ) ;
break ;
}
}
for( int i = 0 ; i < n ; i++ )
{
//cout << i << " " << mp2[ i ] << '\n' ;
}
for( int i = 0 ; i < n ; i++ ) v[ i ].clear() ;
for( int i = 0 ; i < n ; i++ )
{
X[ i ] = mp2[ X[ i ] ] ;
Y[ i ] = mp2[ Y[ i ] ] ;
v[ X[ i ] ].pb( { Y[ i ], Z[ i ] } ) ;
v[ Y[ i ] ].pb( { X[ i ], Z[ i ] } ) ;
}
dfs( mp2[ s ] ) ;
ll mn = 1e9, mx = 0 ;
for( int i = 1 ; i <= q ; i++ )
{
for( int j = 1 ; j <= 5 ; j++ )
{
ll x ;
cin >> x ;
mn = min( mn, mp2[ x ] ) ;
mx = max( mx, mp2[ x ] ) ;
}
cout << pref[ mx ] - pref[ mn ] << '\n' ;
}
}
Compilation message
roadsideadverts.cpp: In function 'void dfs(long long int)':
roadsideadverts.cpp:27:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for( int i = 0 ; i < v[ x ].sz() ; i++ )
| ~~^~~~~~~~~~~~~
roadsideadverts.cpp: In function 'void dfs2(long long int, long long int)':
roadsideadverts.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for( int i = 0 ; i < v[ x ].sz() ; i++ )
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
57620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
69484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
67612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
57620 KB |
Output is correct |
| 2 |
Incorrect |
68 ms |
69484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
