Alpine valley

#include <bits/stdc++.h>

#define debug(x) cout << #x << ": " << x << "\n"
#define all(x) x.begin(), x.end()

using namespace std;
using std::sort;
using ll = long long;

const int N = 1e5 + 1;
const int LOG = 20;
const int M = 101;
const int inf = 1e9;
const ll LLinf = 1e16;

vector<pair<int, ll>> g[N];
vector<pair<int, int>> edges;
int par[N];
bool shop[N];
int jump[N][LOG], depth[N];
ll weight_d[N];


ll up[N];
vector<pair<ll, int>> down[N];


int n, s, q, e;


void first_dfs(int cur, int pre){
    par[cur] = pre;
    jump[cur][0] = pre;
    depth[cur] = depth[pre] + 1;

    for(auto [nex, w] : g[cur]){
        if(nex == pre)continue;
        // cost_jump[nex][0] = w;
        weight_d[nex] = weight_d[cur] + w;
        first_dfs(nex, cur);
    }
}


void create_jump(){

    for(int j = 1; j < LOG; ++j){
        for(int i = 1; i <= n; ++i){
            jump[i][j] = jump[jump[i][j-1]][j-1];
            // cost_jump[i][j] = cost_jump[i][j-1] + cost_jump[jump[i][j-1]][j-1];
        }
    }
}


bool solve(int ind, int node){

    auto [p, c] = edges[ind];
    if(par[c] != p)swap(p, c);
    assert(par[c] == p);
    // cout << p << " " << c << "\n";
    // cout << node << "\n";

    if(c == node)return 0;
    if(depth[c] >= depth[node])return 1;
    
    for(int j = LOG - 1; j >= 0; --j){
        int nex = jump[node][j];
        if(depth[nex] >= depth[c]){
            node = nex;
        }
    }
    // cqout << node << " " << c << "\n\n";

    return node != c;
}


ll calc_down(int cur, int pre){

    if(shop[cur])down[cur].push_back({0, -1});
    else down[cur].push_back({LLinf, -1});


    for(int i = 0; i < (int)g[cur].size(); ++i){
        auto [nex, w] = g[cur][i];
        if(nex == pre)continue;

        down[cur].push_back({calc_down(nex, cur) + w, nex});
    }  
    sort(all(down[cur]));
    return down[cur].begin()->first;
}

void calc_up(int cur, int pre, ll mn_dis){

    if(!shop[cur])up[cur] = mn_dis;

    for(int i = 0; i < (int)g[cur].size(); ++i){
        auto [nex, w] = g[cur][i];
        if(nex == pre)continue;

        ll add = down[cur].begin()->first ;
        if(down[cur].begin()->second == nex)add = down[cur][1].first;

        ll cur_mn = min(mn_dis, add) + w;

        calc_up(nex, cur, cur_mn);
    }
}

int lca(int a, int b){

    if(depth[a] < depth[b])swap(a, b);

    for(int j = LOG - 1; j >= 0; --j){
        int nex = jump[a][j];
        if(depth[nex] >= depth[b]){
            a = nex;
        }
    }

    assert(depth[a] == depth[b]);

    for(int j = LOG - 1; j >= 0; --j){
        while(jump[a][j] != jump[b][j]){
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    if(a == b)return a;
    return jump[a][0];
}


ll dist(int a, int b){

    int c = lca(a, b);

    return weight_d[a] + weight_d[b] - 2ll * weight_d[c];
}


ll calc_min_dis(int ind, int node){

    auto [p, c] = edges[ind];
    if(par[c] != p)swap(p, c);
    assert(par[c] == p);
    
    ll dis = -1;

    assert(lca(node, c) == c);
    // cout << node << " " << p << " " << c << "\n";
    // cout << down[node].begin()->first << "\n";
    // cout << dist(node, c ) << "\n";
    // cout << c << "\n";
    if(node == c){
        dis = down[node].begin()->first;
    }else if(lca(node, c) == c){

        dis = down[node].begin()->first;

        if(up[node] < up[c] + dist(node, c))dis = min(dis, up[node]);
        if(shop[c])dis = min(dis, dist(node, c));

        int node_up = node;
        for(int j = LOG - 1; j >= 0; --j){
            int nex = jump[node_up][j];
            if(depth[nex] > depth[c]){
                node_up = nex;
            }
        }

        // cout << node << " " << node_up << " " << p << " " << c << "\n";

        ll dis_down = down[c].begin()->first;
        if(down[c].begin()->second == node_up){
            dis_down = down[c][1].first;
        }
        dis = min(dis, dist(node, c) + dis_down);


    }

    if(dis > (ll)1e15)return -1;
    return dis;
}


int main(){

    // cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s >> q >> e;
    for(int _ = 0; _ < n - 1; ++_){
        int a, b; ll w; 
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
        edges.push_back({min(a, b), max(a, b)});
    }
    for(int _ = 0; _ < s; ++_){
        int c; cin >> c;
        shop[c] = 1;
    }

    first_dfs(e, 0);
    create_jump();
    calc_down(e, 0);
    calc_up(e, 0, shop[e] ? 0 : LLinf);

    // for(int i = 1; i <= n; ++i){
    //     cout << i << " " << up[i] << " " << down[i].begin()->first << "\n";
    // }

    while(q--){
        int I, R;
        cin >> I >> R;
        if(solve(I-1, R)){
            cout << "escaped\n";
        }else{
            ll res = calc_min_dis(I-1, R);
            if(res == -1)cout << "oo\n";
            else cout << res << "\n";
        }
    }



    // how to check if we can reach the root?
    // The road is cuts our way iff the endpoint
    // (p, c) has depth smaller AND lca(node, c) == p with
    // (note the special case, then we have to check)

    // How to find closest shop? First we can precompute
    // with tree dp to each direction for each node.
    // But how to handle the removal of an edge?
    // 
    // Let the edge removed be (p, c), that is, (parent, child)
    // and the node be a.
    // 
    // if c is an ancestor of a (lca(a, c) == c):
    //      answer is min(down[a], dis(a, c) + down[c])
    // else if p is an ancestor of a (lca(a, p) == p):
    //      answer is min(down[a], dis(a, p) + min(up[p], down[p] (not including the direction to c)))
    // else if p is in the subtree of a:
    //      answer is min(up[a], down[a] (not including direction of p), dis(a, p) - up[p] (if positive), dis(a, p) + down[p] (not including the direction of c))
    // else they just have a lowest common ancestor lca(a, p)
    //      answer is min(down[a], dis(a, lca) + up[lca], dis(a, lca) + down[lca] (not including the direction of p), dis(a, lca) + dis(lca, p) - up[p] (if this is positive))
    // think about the case when a is either p or a!!
    

}

Test 1

Group: 2, 4

Verdict: ACCEPTED

Test 2

Group: 2, 4

Verdict: ACCEPTED

Test 3

Group: 1, 4

Verdict: ACCEPTED

Test 4

Group: 1, 4

Verdict: ACCEPTED

Test 5

Group: 1, 4

Verdict: ACCEPTED

Test 6

Group: 1, 3, 4

Verdict: ACCEPTED

Test 7

Group: 2, 4

Verdict: ACCEPTED

Test 8

Group: 2, 4

Verdict: ACCEPTED

Test 9

Group: 2, 4

Verdict: ACCEPTED

Test 10

Group: 2, 4

Verdict: ACCEPTED

Test 11

Group: 2, 4

Verdict: ACCEPTED

Test 12

Group: 2, 4

Verdict: ACCEPTED

Test 13

Group: 2, 3, 4

Verdict: ACCEPTED

Test 14

Group: 2, 3, 4

Verdict: ACCEPTED

Test 15

Group: 2, 3, 4

Verdict: ACCEPTED

Test 16

Group: 2, 4

Verdict: ACCEPTED

Test 17

Group: 3, 4

Verdict: ACCEPTED

Test 18

Group: 3, 4

Verdict: ACCEPTED

Test 19

Group: 3, 4

Verdict: ACCEPTED

Test 20

Group: 3, 4

Verdict: ACCEPTED

Test 21

Group: 3, 4

Verdict: ACCEPTED

Test 22

Group: 3, 4

Verdict: ACCEPTED

Test 23

Group: 4

Verdict: ACCEPTED

Test 24

Group: 4

Verdict: ACCEPTED

Test 25

Group: 4

Verdict: ACCEPTED

Test 26

Group: 4

Verdict: ACCEPTED

Test 27

Group: 4

Verdict: ACCEPTED

Test 28

Group: 4

Verdict: ACCEPTED

Test 29

Group: 4

Verdict: WRONG ANSWER

Test 30

Group: 4

Verdict: WRONG ANSWER

Test 31

Group: 4

Verdict: WRONG ANSWER

Test 32

Group: 4

Verdict: ACCEPTED

Test 33

Group: 4

Verdict: WRONG ANSWER

Test 34

Group: 4

Verdict: WRONG ANSWER

Test 35

Group: 4

Verdict: WRONG ANSWER

Test 36

Group: 4

Verdict: WRONG ANSWER

Test 37

Group: 4

Verdict: ACCEPTED

Test 38

Group: 4

Verdict: ACCEPTED