Chcemy złapać mysz, która porusza się po wierzchołkach drzewa. Każda krawędź może być czysta, brudna albo zablokowana. My w swoim ruchu możemy (ale nie musimy) wykonać jedną operację: zablokować krawędź lub oczyścić brudną krawędź. Następnie mysz w swoim ruchu wybiera jakąś czystą krawędź wychodzącą z wierzchołka, w którym się znajduje (o ile jest taka), i przechodzi nią, brudząc ją. Ile minimalnie operacji musimy zrobić, aby zagonić mysz z wierzchołka $v_S$ do wierzchołka $v_E$ (niezależnie od jej ruchów)?

Zarys strategii

Dopóki mysz ma do wyboru różne czyste krawędzie, to nie bardzo jesteśmy w stanie kontrolować jej ruchy. Możemy jednak pozwolić jej się wybiegać; będzie wtedy brudzić kolejne krawędzie i w pewnym momencie utknie bez możliwości ruchu. Wtedy możemy oczyścić ścieżkę z aktualnej pozycji myszy do wierzchołka $v_E$, wcześniej blokując wszystkie czyste krawędzie dochodzące do tej ścieżki. Mysz nie będzie miała wyboru i przejdzie całą oczyszczoną ścieżkę.

Przypadek prostszy

W podzadaniu 2 mamy założenie, że wierzchołki $v_S$ i $v_E$ są połączone krawędzią. Jasne jest, że uciekająca mysz nie wybierze tej krawędzi w swoim pierwszym ruchu, jeśli ma inne krawędzie z $v_S$. Możemy więc na chwilę usunąć tę krawędź. Jedną z pozostałych części jest poddrzewo zaczepione w $v_E$, które też nie ma znaczenia, bo po wejściu do $v_E$ gra się kończy.

Zatem zostaje poddrzewo zaczepione w $v_S$. Robimy teraz programowanie dynamiczne. Dla wierzchołka $v$ obliczamy minimalną liczbę operacji $dp[v]$, które musimy wykonać, aby zmusić mysz do przejścia krawędzią z $v$ do jego ojca (zakładając, że ta krawędź jest czysta).

Jeśli $v$ jest liściem, to $dp[v]=0$. Jeśli $v$ ma jedno dziecko $u$, to $dp[v]=1$, bo wystarczy, że zablokujemy krawędź do tego dziecka.

Załóżmy zatem, że $v$ ma $s$ dzieci $u_1, \ldots, u_s$, które są posortowane względem liczby operacji potrzebnych w ich poddrzewach, żeby mysz wróciła do $v$: $dp[u_1] \geq dp[u_2] \geq \ldots \geq dp[u_s]$.

Jeśli mysz przejdzie do dowolnego $u_i$, to będziemy potrzebować $dp[u_i]$ operacji, żeby mysz zawróciła w $u_i$. Ponieważ chcemy, żeby przeszła z $u_i$ do $v$, to musimy oczyścić tę krawędź, oraz zablokować krawędzie do pozostałych dzieci. Zatem będziemy potrzebować w sumie $s + dp[u_i]$ operacji.

Zauważmy jednak, że możemy jedną operację blokady wykonać przed ruchem myszy, zatem najbardziej opłaca się zablokować dziecko $u_1$, mysz wtedy wybierze drugie maksimum, czyli $u_2$. Tak więc ostatecznie $dp[v] = s + dp[u_2]$. Zauważmy, że nie potrzebujemy tutaj sortowania wierzchołków, wystarczy znaleźć drugie maksimum (co łatwo zrobić w czasie liniowym od liczby dzieci).

Odpowiedzią do zadania jest $dp[v_S]$, a algorytm ma złożoność $O(n)$.

const int N = 1100000;
int n,ve,vs;
vector<int> adj[N];
int dp[N];

void dfs(int v, int par) {
  if (v == ve) {
    dp[v] = -2;
    return;
  }

  int m1=-1, m2=-1;
  int s=0;
  for (int u : adj[v]) if (u != par) {
    dfs(u, v);
    if (dp[u] >= m1) {
      m2 = m1; m1 = dp[u];
    } else if (dp[u] >= m2) {
      m2 = dp[u];
    }
    s += u != ve;
  }
  if (m1 == -1) dp[v] = 0;
  else if (m2 == -1) dp[v] = 1;
  else dp[v] = s + m2;
}

int main() {
  scanf("%d%d%d",&n,&ve,&vs);
  --ve; --vs;
  REP(i,n-1) {
    int a,b; scanf("%d%d",&a,&b);
    --a; --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs(vs, -1);
  int ans = dp[vs];

  printf("%d\n", ans);
}