G. Rikka with Intersections of Paths

Codeforces

IDCF10201G

Time6000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Rikka has a tree $T$ with $n$ vertices numbered from $1$ to $n$. Meanwhile, Rikka has marked $m$ simple paths in $T$, the $i$-th of which is between the vertices $x_i$ and $y_i$, where some of them could be the same path. Now, Rikka wants to know in how many different strategies she can select $k$ paths from the marked paths such that those selected paths share at least one common vertex. The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 200$), the number of test cases. For each test case, the first line contains three integers $n$ ($1 <= n <= 3 times 10^5$), the size of the tree $T$, $m$ ($2 <= m <= 3 times 10^5$), the number of marked paths, and $k$ ($2 <= k <= m$). The following $(n -1)$ lines describe the tree $T$. Each of them contains two integers $u$ and $v$ ($1 <= u, v <= n$, $u != v$), representing an edge between the vertices $u$ and $v$. The following $m$ lines describe all marked simple paths in the tree. The $i$-th of them contains two integers $x_i$ and $y_i$ ($1 <= x_i, y_i <= n$). The input guarantees that the sum of $n$ and the sum of $m$ in all test cases are at most $2 times 10^6$ respectively. For each test case, output a single line with a single integer, the number of different strategies meeting the requirement modulo $(10^9 + 7)$. ## Input The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 200$), the number of test cases.For each test case, the first line contains three integers $n$ ($1 <= n <= 3 times 10^5$), the size of the tree $T$, $m$ ($2 <= m <= 3 times 10^5$), the number of marked paths, and $k$ ($2 <= k <= m$).The following $(n -1)$ lines describe the tree $T$. Each of them contains two integers $u$ and $v$ ($1 <= u, v <= n$, $u != v$), representing an edge between the vertices $u$ and $v$.The following $m$ lines describe all marked simple paths in the tree. The $i$-th of them contains two integers $x_i$ and $y_i$ ($1 <= x_i, y_i <= n$).The input guarantees that the sum of $n$ and the sum of $m$ in all test cases are at most $2 times 10^6$ respectively. ## Output For each test case, output a single line with a single integer, the number of different strategies meeting the requirement modulo $(10^9 + 7)$. [samples]

**Definitions** Let $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $. Let $ \mathcal{P} = \{P_1, P_2, \dots, P_m\} $ be a multiset of simple paths in $ T $, where each $ P_i $ connects vertices $ x_i $ and $ y_i $. Let $ k \in \mathbb{Z} $, $ 2 \leq k \leq m $. **Constraints** 1. $ 1 \leq T \leq 200 $ (number of test cases). 2. For each test case: - $ 1 \leq n \leq 3 \times 10^5 $, $ 2 \leq m \leq 3 \times 10^5 $, $ 2 \leq k \leq m $. - The sum of all $ n $ across test cases $ \leq 2 \times 10^6 $. - The sum of all $ m $ across test cases $ \leq 2 \times 10^6 $. **Objective** Compute the number of $ k $-subsets $ \mathcal{S} \subseteq \mathcal{P} $, $ |\mathcal{S}| = k $, such that $ \bigcap_{P \in \mathcal{S}} P \neq \emptyset $, i.e., all paths in $ \mathcal{S} $ share at least one common vertex. Output the result modulo $ 10^9 + 7 $.

API Response (JSON)

{
  "problem": {
    "name": "G. Rikka with Intersections of Paths",
    "description": {
      "content": "Rikka has a tree $T$ with $n$ vertices numbered from $1$ to $n$. Meanwhile, Rikka has marked $m$ simple paths in $T$, the $i$-th of which is between the vertices $x_i$ and $y_i$, where some of them c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10201G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Rikka has a tree $T$ with $n$ vertices numbered from $1$ to $n$.\n\nMeanwhile, Rikka has marked $m$ simple paths in $T$, the $i$-th of which is between the vertices $x_i$ and $y_i$, where some of them c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $.  \nLet $ \\mathcal{P} = \\{P_1, P_2, \\dots, P_m\\} $ be a multiset of simple paths in $ T $, where each $ P_i $ connects ver...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments