Statement : E0. Graph Cutting (Two Vertices, Any Size)
Tutorial version of E. Graph Cutting. Here Fedya picks only two vertices. Pair chain: E0 (here) → E1 → E2. Triplet chain: E3 → E4 → E.
You are given a tree with $n$ vertices and two distinct vertices $a$ and $b$. A connected subgraph is a non-empty set of vertices $S$ such that the induced subgraph on $S$ is connected. (Equivalently: $S$ is connected in the tree.)
Count how many connected subgraphs contain both $a$ and $b$. Two subgraphs are different if their vertex sets differ.
The first line contains an integer $t$ ($1 \le t \le 500$) — the number of test cases.
Each test case:
- One line: $n$, $a$, $b$ ($2 \le n \le 2000$, $1 \le a, b \le n$, $a \ne b$).
- Then $n - 1$ lines: edges $u$, $v$ ($1 \le u, v \le n$, $u \ne v$). The graph is a tree.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.
For each test case, print the number of connected subgraphs that contain both $a$ and $b$, modulo $998244353$.
Input
3
4 2 3
1 2
3 1
4 1
5 1 5
1 2
2 4
2 3
5 1
4 2 4
1 2
3 1
4 1
Output
2
5
2
Note
- Test 1: path $2 \text{–} 1 \text{–} 3$ is mandatory; vertex $4$ may or may not be added. Subgraphs: $\{2,1,3\}$ and $\{2,1,3,4\}$.
- Test 2: path $1 \text{–} 5$ is mandatory; any connected subset of the $2 \text{–} \{3,4\}$ branch may be added independently ($4$ choices for that branch, plus the empty choice → $5$ total).
- Test 3: same star as in E example 1; only $\{2,1,4\}$ and $\{2,1,3,4\}$ contain both $2$ and $4$.