#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
using namespace std;
const long long oo = 1000000000000000000;
long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
/*
ViHHiPuh
(( `'-""``""-'` ))
)-__-_.._-__-(
/ --- (o _ o) --- \
\ .-* ( .0. ) *-. /
_'-. ,_ '=' _, .-'_
/ `;#'#'# - #'#'#;` \
\_)) -----'#'----- ((_/
# --------- #
'# ------- ------ #'
/..-'# ------- #'-.\
_\...-\'# -- #'/-.../_
((____)- '#' -(____))
cout << fixed << setprecision(6) << x;
freopen ( "sum.in", "r", stdin )
*/
int n, m, q, st, par[ 100001 ][ 21 ], lg = 20, d[ 100001 ], prr[ 100001 ], b[ 100001 ];
vector <pair<int, int> > v[ 100001 ];
queue <int> vv;
vector <int> v1;
int tmr, tin[ 100001 ], tout[ 100001 ], col[ 100001 ], t[ 400001 ], p[ 400001 ], tt[ 400001 ];
pair <int, int> e[ 100001 ];
void dfs( int u, int pr ) {
par[ u ][ 0 ] = pr;
tin[ u ] = ++tmr;
v1.push_back( u );
for ( int i = 1; i <= lg; i ++ )
par[ u ][ i ] = par[ par[ u ][ i - 1 ] ][ i - 1 ];
for ( auto to : v[ u ] ) {
if ( to.first != pr ) {
prr[ to.first ] = to.second;
d[ to.first ] = d[ u ] + to.second;
dfs( to.first, u );
}
}
tout[ u ] = tmr;
}
bool ok( int a, int b ) {
return ( tin[ a] <= tin[ b ] && tout[ a ] >= tout[ b ] );
}
int lca( int a, int b ) {
if ( ok( a, b ) )
return a;
if ( ok( b, a ) )
return b;
for ( int i = lg; i >= 0; i -- ) {
if ( !ok( par[ a ][ i ], b ) )
a = par[ a ][ i ];
}
return par[ a ][ 0 ];
}
void pus( int v ) {
if ( p[ v ] ) {
p[ v + v ] += p[ v ];
p[ v + v + 1 ] += p[ v ];
t[ v + v ] += p[ v ];
t[ v + v + 1 ] += p[ v ];
}
}
void gett( int v, int tl, int tr, int l, int r ) {
if ( tl > r || tr < l )
return;
if ( tl >= l && tr <= r ) {
if ( num > t[ v ] ) {
num = t[ v ];
pos = tt[ v ];
}
return;
}
pus( v );
int mid = ( tl + tr ) / 2;
gett( v + v, tl, mid, l, r );
gett( v + v + 1, mid + 1, tr, l, r );
}
void dfs1( int u, int pr ) {
for ( auto to : v[ u ] ) {
if ( to.first != pr ) {
if ( col[ to.first ] > col[ u ] + to.second ) {
col[ to.first ] = col[ u ] + to.second;
vv.push( to.first );
}
dfs1( to.first, u );
}
}
}
void build( int v, int tl, int tr ) {
if ( tl == tr ) {
t[ v ] = col[ tl ];
tt[ v ] = tl;
return;
}
int mid = ( tl + tr ) / 2;
build( v + v, tl, mid );
build( v + v + 1, mid + 1, tr );
t[ v ] = min( t[ v + v ], t[ v + v + 1 ] );
if ( t[ v ] == t[ v + v ] )
tt[ v ] = tt[ v + v ];
else
tt[ v ] = tt[ v + v + 1 ];
}
main () {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q >> st;
int x, y, z;
for ( int i = 1; i < n; i ++ ) {
cin >> x >> y >> z;
v[ x ].push_back( { y, z } );
v[ y ].push_back( { x, z } );
e[ i ] = { x, y };
}
for ( int i = 1; i <= n; i ++ )
col[ i ] = oo;
dfs( st, st );
for ( int i = 1; i <= m; i ++ ) {
cin >> x;
col[ x ] = 0;
b[ x ] = 1;
vv.push( x );
}
while ( vv.size() ) {
if ( col[ par[ vv.front() ][ 0 ] ] > col[ vv.front() ] + prr[ vv.front() ] ) {
col[ par[ vv.front() ][ 0 ] ] = min( col[ vv.front() ] + prr[ vv.front() ], col[ par[ vv.front() ][ 0 ] ] );
vv.push( par[ vv.front() ][ 0 ] );
}
vv.pop();
}
for ( int i = 1; i <= n; i ++ ) {
if ( col[ i ] != oo )
col[ i ] -= d[ i ];
}
build( 1, 1, n );
int l, r, ll, rr;
while ( q -- ) {
cin >> l >> r;
// cout << l << " " << r << " ";
sum = ans = num = 0;
if ( d[ e[ l ].first ] < d[ e[ l ].second ] ) {
num = e[ l ].first;
sum = e[ l ].second;
}
else {
num = e[ l ].second;
sum = e[ l ].first;
}
ans = lca( r, sum );
// cout << ans << " " << sum << " - ";
if ( ans != sum ) {
cout << "escaped\n";
}
else {
if ( col[ sum ] == oo ) {
cout << "oo\n";
}
else {
if ( !b[ r ] ) {
ll = tin[ sum ];
rr = tout[ sum ];
num = oo;
pos = 0;
gett( 1, 1, n, ll, rr );
// cout << num << " - ";
num += d[ r ];
num += d[ lca( pos, r ) ];
}
else
num = 0;
cout << num << "\n";
}
}
}
}
/*
8 8 10 2
1 2 1
2 3 1
3 4 1
2 5 1
5 8 1
3 6 1
7 4 1
1 2 3 4 5 6 7 8
2 7
1 1
4 8
2 6
6 6
3 3
7 6
2 2
5 5
1 1
1 1
1 1
1 1
1 1
*/
Compilation message
valley.cpp:137:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
137 | main () {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
36856 KB |
Output is correct |
| 2 |
Correct |
177 ms |
36800 KB |
Output is correct |
| 3 |
Correct |
163 ms |
36872 KB |
Output is correct |
| 4 |
Correct |
205 ms |
38372 KB |
Output is correct |
| 5 |
Correct |
197 ms |
38492 KB |
Output is correct |
| 6 |
Correct |
188 ms |
40352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
