Dane jest $N$-wierzchołkowe drzewo ważone ukorzenione w wierzchołku $r$ oraz wybrany podzbiór wierzchołków $S$.
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$.
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 $tin[v]$ oraz czas wyjścia $tout[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 $$tin[u] \leq tin[v] \quad\text{oraz}\quad tout[v] \leq tout[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"); } } }
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 $down(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 = LCA(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ść $dist(v,w) + down(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} dist(v,w) + down(w)$, gdzie sumowanie przebiega po wszystkich wierzchołkach $w$ ze ścieżki od $v$ do $u$ (włącznie).
Wszystkie wartości $down(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)$.