Mamy też $Q$ zapytań, każde postaci $e, v$ oznaczające: „jeśli usuniemy krawędź $e$ , to czy będziemy w stanie dojść z wierzchołka $v$ do korzenia, a jeśli nie, to jaka jest najkrótsza droga z $v$ do wierzchołka ze zbioru $S$ .

Podzadanie 3

W tym podzadaniu rozmiar podzbioru $S$ wynosi $N$ , zatem wszystkie wierzchołki do niego należą. Tak więc jeśli w zapytaniu $e, v$ nie da się dojść z $v$ do korzenia, to odpowiedź wynosi 0, bo $v$ należy do $S$ , zatem droga jest pusta.

Wystarczy zatem odpowiadać na zapytania: „jeśli usuniemy krawędź $e$ , to czy będziemy w stanie dojść z $v$ do korzenia”. Takie zapytanie jest równoważne: „czy $v$ nie należy do poddrzewa zaczepionego w dolnym wierzchołku krawędzi $e$ ”.

Przynależność wierzchołka do poddrzewa jest klasycznym problemem na drzewie, który można rozwiązać przy pomocy DFS-a. Dla każdego wierzchołka $v$ wyznaczamy czas wejścia $t i n [v]$ oraz czas wyjścia $t o u t [v]$ , będące pierwszym i ostatnim momentem, w którym ten wierzchołek jest odwiedzany przez procedurę DFS. Nietrudno zobaczyć, że wierzchołek $v$ zawiera się w poddrzewie zaczepionym w wierzchołku $u$ , jeśli $t i n [u] \leq t i n [v] oraz t o u t [v] \leq t o u t [u] .$

Poniższy algorytm implementuje rozwiązanie w czasie $O (N + Q)$ :

const int N = 110000;
int n,s,q,root,shop[N];
vector<pii> adj[N];
int ea[N],eb[N],ew[N];
int lev[N],tin[N],tout[N],T;

void dfs(int v, int par, int l) {
  lev[v] = l;
  tin[v] = T++;
  for (auto [u, w] : adj[v]) if (u != par) {
    dfs(u, v, l+1);
  }
  tout[v] = T;
}

bool is_desc(int v, int w) {
  return tin[v] <= tin[w] && tout[w] <= tout[v];
}

int main() {
  scanf("%d%d%d%d",&n,&s,&q,&root); --root;
  REP(i,n-1) {
    int a,b,w; scanf("%d%d%d",&a,&b,&w);
    --a; --b;
    adj[a].emplace_back(b, w);
    adj[b].emplace_back(a, w);
    ea[i] = a;
    eb[i] = b;
    ew[i] = w;
  }
  REP(i,s) {
    int a; scanf("%d",&a); --a;
    shop[a] = 1;
  }

  dfs(root, -1, 0);

  for (int i=0; i<q; ++i) {
    int r,a; scanf("%d%d",&r,&a);
    --r; --a;

    int vb = lev[ea[r]] < lev[eb[r]] ? eb[r] : ea[r];
    if (is_desc(vb, a)) {
      printf("0\n");
    } else {
      printf("escaped\n");
    }
  }
}

Pełne rozwiązanie

W przypadku nietrywialnego zbioru $S$ , sprawdzenie, czy da się dojść z $v$ do korzenia jest takie same, jak poprzednio. Zatem pozostaje nam kwestia obliczenia najkrótszej drogi z $v$ do wierzchołka z podzbioru $S_{u} \subseteq S$ zawartego w poddrzewie zaczepionym w $u$ (dolnym wierzchołku krawędzi $e$ ).

Część wierzchołków z $S_{u}$ zawiera się w poddrzewie zaczepionym w $v$ (czyli jest to zbiór $S_{v}$ ). Wyznaczenie najbliższego wierzchołka z $S_{v}$ do $v$ można zrobić prostym programowaniem dynamicznym po drzewie (dla każdego wierzchołka obliczamy odległość do najbliższego z poddrzewa). Oznaczmy tę wartość przez $d o w n (v)$ .

Załóżmy zatem, że $s \in S_{u}$ nie jest w $S_{v}$ . Wtedy ścieżka z $v$ do $s$ idzie najpierw w górę (do wierzchołka $w = L C A (v, s)$ ), a następnie w dół. Zauważmy, że możemy hurtowo rozważyć wszystkie $s \in S_{u}$ , które mają ten sam wierzchołek $w$ jako najwyższy wierzchołek ścieżki do $v$ . Najkrótsza ścieżka bowiem będzie miała długość $d i s t (v, w) + d o w n (w)$ . Zauważmy, że w tym wzorze uwzględniamy również pewne zdegenerowane ścieżki (np. idące z $v$ do $w$ , a potem wracające po tych samych krawędziach z powrotem do poddrzewa zaczepionego w $v$ ), ale one nam nie przeszkadzają, bo na pewno nie będą najkrótsze.

Podsumowując, odpowiedzią na zapytanie jest $min_{w} d i s t (v, w) + d o w n (w)$ , gdzie sumowanie przebiega po wszystkich wierzchołkach $w$ ze ścieżki od $v$ do $u$ (włącznie).

Wszystkie wartości $d o w n (v)$ można obliczyć programowaniem dynamicznym w czasie $O (N)$ . Aby minimum obliczać w czasie $O (\log N)$ , posłużymy się tutaj standardową metodą „binary lifting”. Szczegóły w kodzie:

const int N = 110000, LOGN = 17;
const ll infty = 1e18;
int n,s,q,root,shop[N];
vector<pii> adj[N];
int ea[N],eb[N],ew[N];
int lev[N],tin[N],tout[N],T;
ll down[N];
int parent[N],pw[N];

int jmp[LOGN][N];
ll jmp_w[LOGN][N], jmp_c[LOGN][N];

void dfs(int v, int par, int l) {
  lev[v] = l;
  tin[v] = T++;
  down[v] = shop[v] ? 0 : infty;
  parent[v] = par;
  for (auto [u, w] : adj[v]) if (u != par) {
    dfs(u, v, l+1);
    pw[u] = w;
    down[v] = min(down[v], w + down[u]);
  }
  tout[v] = T;
}

bool is_desc(int v, int w) {
  return tin[v] <= tin[w] && tout[w] <= tout[v];
}

int main() {
  scanf("%d%d%d%d",&n,&s,&q,&root); --root;
  REP(i,n-1) {
    int a,b,w; scanf("%d%d%d",&a,&b,&w);
    --a; --b;
    adj[a].emplace_back(b, w);
    adj[b].emplace_back(a, w);
    ea[i] = a;
    eb[i] = b;
    ew[i] = w;
  }
  REP(i,s) {
    int a; scanf("%d",&a); --a;
    shop[a] = 1;
  }

  dfs(root, n, 0);
  parent[n] = n;

  REP(i,n+1) {
    jmp[0][i] = parent[i];
    jmp_w[0][i] = pw[i];
    jmp_c[0][i] = pw[i] + down[parent[i]];
  }
  REP(f,LOGN-1) {
    REP(i,n+1) {
      int mid = jmp[f][i];
      jmp[f+1][i] = jmp[f][mid];
      jmp_w[f+1][i] = jmp_w[f][i] + jmp_w[f][mid];
      jmp_c[f+1][i] = min( jmp_c[f][i], jmp_w[f][i] + jmp_c[f][mid] );
    }
  }

  for (int i=0; i<q; ++i) {
    int r,a; scanf("%d%d",&r,&a);
    --r; --a;

    int vb = lev[ea[r]] < lev[eb[r]] ? eb[r] : ea[r];
    if (is_desc(vb, a)) {

      ll ans = down[a], len = 0;
      int v = a;
      int dist = lev[v] - lev[vb];
      REP(f,LOGN) if (dist & 1<<f) {
        ans = min(ans, len + jmp_c[f][v]);
        len += jmp_w[f][v];
        v = jmp[f][v];
      }

      if (ans == infty) {
        printf("oo\n");
      } else {
        printf("%lld\n", ans);
      }
    } else {
      printf("escaped\n");
    }
  }
}

Złożoność czasowa rozwiązania to $O ((N + Q) \log N)$ .