#include <bits/stdc++.h>
using namespace std;
#define int __int128
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll n, s, q, e;
int S[300005], E[300005], stuf[300050], cnt = 1;
vector <pi> adj[300005];
int U[300005], V[300005], dep[300005], mn[300005], fin[300005], head[300005], up[300005], sz[300005], val[300005], pa[20][200005], f, ans;
pi blk;
void dfs(int x, int p, int d){
dep[x] = d;
up[x] = p;
pa[0][x] = p;
sz[x] = 1;
for(auto [i, j] : adj[x]){
if(i == p)continue;
dfs(i, x, d + 1);
sz[x] += sz[i];
}
}
struct node{
int s,e,m,val, lazy = 0;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e)>>1;
val = 0;
if(s != e)l = new node(s, m), r = new node(m+1, e);
}
void propo(){
if(lazy){
val += lazy;
if(s != e)l->lazy += lazy, r->lazy += lazy;
lazy = 0;
}
}
void upd(int a, int b, int c){
//cerr << "UPD " << a << " " << b << " " << c << '\n';
if(a == s && b == e)lazy += c;
else{
if(b <= m)l->upd(a, b, c);
else if(a > m)r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m+1, b, c);
l->propo(), r->propo();
val = min(l->val, r->val);
}
}
int query(int a, int b){
if(a > b)return 1e18;
propo();
if(a == s && b == e)return val;
else if( b <= m)return l->query(a, b);
else if(a > m)return r->query(a, b);
else return min(l->query(a, m), r->query(m+1, b));
}
}*root, *root2;
void dfs2(int x, int h, int par){
S[x] = cnt++;
head[x] = h;
int maxi = 0, in = -1;
for(auto [i, j] : adj[x]){
if(i == par)continue;
if(maxi < sz[i])maxi = sz[i], in = i;
}
for(auto [i, j] : adj[x]){
if(i == par)continue;
if(i == in)dfs2(i, h, x);
}
for(auto [i, j] : adj[x]){
if(i != par && i != in)dfs2(i, i, x);
}
E[x] = cnt - 1;
}
int query(int a, int b) {
int res = 1e18;
for (; head[a] != head[b]; b = up[head[b]]) {
if (dep[head[a]] > dep[head[b]])
swap(a, b);
int cur_heavy_path_max = root->query(S[head[b]], S[b]);
res = min(res, cur_heavy_path_max);
}
if (dep[a] > dep[b])
swap(a, b);
res = min(res, root->query(S[a], S[b]));
return res;
}
//across all parents,
//ans[v] = min(mn[u] - 2 * dep[u]) + dep[v]
void dfs3(int x, int par, int cur){
val[x] = cur;
mn[x] = (stuf[x] ? val[x] : 1e18);
for(auto [i, j] : adj[x]){
if(i == par)continue;
dfs3(i, x, cur + j);
mn[x] = min(mn[x], mn[i]);
}
}
int cry[300005];
void dfs4(int x, int par){
if(x == 1)cry[x] = 1e18;
if(stuf[x])cry[x] = min(cry[x], val[x]);
multiset <int> ms;
for(auto [i, j] : adj[x]){
if(i == par)continue;
ms.insert(mn[i] + j);
}
for(auto [i, j] : adj[x]){
if(i == par)continue;
ms.erase(ms.find(mn[i] + j));
ms.insert(cry[x] + j);
cry[i] = *ms.begin();
ms.insert(mn[i] + j);
ms.erase(ms.find(cry[x] + j));
}
for(auto [i, j] : adj[x])if(i != par)dfs4(i, x);
}
vector <pii> qu[300005];
int lca(int u, int v){
if(dep[u] > dep[v])swap(u, v);
int df = dep[v] - dep[u];
for(int i = 0; i <= 19; i++)if(df >> i & 1)v = pa[i][v];
if(u == v)return u;
for(int i = 19; i >= 0; i--)if(pa[i][u] != pa[i][v])u = pa[i][u], v = pa[i][v];
return pa[0][u];
}
void solve(){
cin >> n >> s >> q >> e;
for(int i = 1; i < n; i++){
ll a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
U[i] = a, V[i] = b;
}
for(int i = 1; i <= s; i++){
ll x; cin >> x; stuf[x] = 1;
}
dfs(1, -1, 1);
dfs2(1, 1, -1);
root = new node(1, n);
root2 = new node(1, n);
dfs3(1, -1, 0);
dfs4(1, -1);
for(int i = 1; i <= 19; i++)for(int j = 1; j <= n; j++)pa[i][j] = pa[i-1][pa[i-1][j]];
for(int i = 1; i <= n; i++)root->upd(S[i], S[i], mn[i] - 2 * val[i]), root2->upd(S[i], S[i], (stuf[i] ? val[i] : 1e18));
//for(int i = 1; i <= n; i++)cout << (ll)cry[i] << ' ';
//cout << '\n';
for(int i = 1; i <= q; i++){
ll a, b; cin >> a >> b;
int tmp = (S[U[a]] < S[V[a]] ? V[a] : U[a]);
if((S[e] >= S[tmp] && E[e] <= E[tmp]) == (S[b] >= S[tmp] && E[b] <= E[tmp]))fin[i] = -1;
else {
if(S[b] >= S[tmp] && E[b] <= E[tmp])fin[i] = query(tmp, b) + val[b];
else{
int bruh = lca(tmp, b);
qu[bruh].push_back({b, {tmp, i}});
ll df = dep[b] - dep[bruh] - 1;
df = max(df, 0ll);
int cur = b;
for(int j = 19; j >= 0; j--)if(df >> j & 1)cur = pa[j][cur];
fin[i] = min(cry[bruh] - val[bruh], (b == bruh ? (int)1e18 : query(cur, b))) + val[b];
//cout << (ll)fin[i] << ' ';
fin[i] = min(fin[i], min(root2->query(S[bruh], S[tmp] - 1), root2->query(E[tmp] + 1, E[bruh])) - val[bruh] * 2 + val[b]);
}
}
}
//dfs5(1, -1);
for(int i = 1; i <= q; i++){
if(fin[i] == -1)cout << "escaped\n";
else if(fin[i] >= 1e16)cout << "oo\n";
else cout << (ll)fin[i] << '\n';
}
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
valley.cpp:191:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
191 | main(){
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
82776 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
82776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
82776 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
82776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
390 ms |
180712 KB |
Output is correct |
| 2 |
Correct |
407 ms |
180496 KB |
Output is correct |
| 3 |
Correct |
455 ms |
181072 KB |
Output is correct |
| 4 |
Correct |
584 ms |
188712 KB |
Output is correct |
| 5 |
Correct |
459 ms |
187216 KB |
Output is correct |
| 6 |
Correct |
464 ms |
187616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
82776 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
82776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
