o64_feb_c2_emer

#include "emergency.h"
#include <bits/stdc++.h>

using namespace std;
const int inf = 1e9;
const int MXN = 2e5 + 5;
using pi = pair <int, int>;
vector <pi> g[MXN];
bool isA[MXN], isB[MXN];
int ans, sub[MXN], node[MXN];

void dfs1(int u, int p){
    if(isA[u]) sub[u] = 0;
    for(auto vw: g[u]){
        int v = vw.first, w = vw.second;
        if(v == p) continue;
        dfs1(v, u);
        if(sub[v] != -inf) sub[u] = max(sub[u], sub[v] + w);
    }
}

void dfs2(int u, int p){

    if(isA[u]) node[u] = max(node[u], 0);
    if(isB[u]) ans = max({ans, sub[u], node[u]});

    int mx1 = -inf, mx2 = -inf, idx = 0;
    for(auto vw: g[u]){
        int v = vw.first, w = vw.second;
        if(v == p) continue;
        int cur = sub[v] + w;
        if(cur > mx1){
            mx2 = mx1;
            mx1 = cur;
            idx = v;
        }
        else if(cur > mx2) mx2 = cur;

        if(node[u] != -inf) node[v] = node[u] + w;
    }

    for(auto vw: g[u]){
        int v = vw.first, w = vw.second;
        if(v == p) continue;
        if(v == idx) node[v] = max(node[v], mx2 + w);
        else node[v] = max(node[v], mx1 + w);
        dfs2(v, u);
    }
}

int furthest(int N, int nA, int nB, int roads[][2], int w[], int A[], int B[]){

    for(int i=0;i<N-1;i++){
        int u = roads[i][0] + 1, v = roads[i][1] + 1;
        g[u].push_back({v, w[i]});
        g[v].push_back({u, w[i]});
    }

    for(int i=0;i<nA;i++)
        isA[ A[i] + 1] = true;

    for(int i=0;i<nB;i++)
        isB[ B[i] + 1] = true;

    for(int u=1;u<=N;u++) sub[u] = node[u] = -inf;

    dfs1(1, -1), dfs2(1, -1);

    return ans;
}