F. Tree nesting

Codeforces
IDCF762F
Time2000ms
Memory256MB
Difficulty—
combinatoricsgraphstrees
English · Original
Chinese · Translation
Formal · Original
You are given two trees (connected undirected acyclic graphs) _S_ and _T_. Count the number of subtrees (connected subgraphs) of _S_ that are isomorphic to tree _T_. Since this number can get quite large, output it modulo 109 + 7. Two subtrees of tree _S_ are considered different, if there exists a vertex in _S_ that belongs to exactly one of them. Tree _G_ is called isomorphic to tree _H_ if there exists a bijection _f_ from the set of vertices of _G_ to the set of vertices of _H_ that has the following property: if there is an edge between vertices _A_ and _B_ in tree _G_, then there must be an edge between vertices _f_(_A_) and _f_(_B_) in tree _H_. And vice versa — if there is an edge between vertices _A_ and _B_ in tree _H_, there must be an edge between _f_ - 1(_A_) and _f_ - 1(_B_) in tree _G_. ## Input The first line contains a single integer |_S_| (1 ≤ |_S_| ≤ 1000) — the number of vertices of tree _S_. Next |_S_| - 1 lines contain two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ |_S_|) and describe edges of tree _S_. The next line contains a single integer |_T_| (1 ≤ |_T_| ≤ 12) — the number of vertices of tree _T_. Next |_T_| - 1 lines contain two integers _x__i_ and _y__i_ (1 ≤ _x__i_, _y__i_ ≤ |_T_|) and describe edges of tree _T_. ## Output On the first line output a single integer — the answer to the given task modulo 109 + 7. [samples]
给定两棵树（连通无向无环图）#cf_span[S] 和 #cf_span[T]。 计算树 #cf_span[S] 中与树 #cf_span[T] 同构的子树（连通子图）的数量。由于这个数可能很大，请输出其对 #cf_span[109 + 7] 取模的结果。 树 #cf_span[S] 的两个子树被认为是不同的，当且仅当存在一个顶点属于其中一个子树但不属于另一个。 树 #cf_span[G] 被称为与树 #cf_span[H] 同构，当且仅当存在一个双射 #cf_span[f]，将 #cf_span[G] 的顶点集映射到 #cf_span[H] 的顶点集，满足以下性质：如果在树 #cf_span[G] 中顶点 #cf_span[A] 和 #cf_span[B] 之间有边，则在树 #cf_span[H] 中顶点 #cf_span[f(A)] 和 #cf_span[f(B)] 之间也必须有边；反之，如果在树 #cf_span[H] 中顶点 #cf_span[A] 和 #cf_span[B] 之间有边，则在树 #cf_span[G] 中顶点 #cf_span[f - 1(A)] 和 #cf_span[f - 1(B)] 之间也必须有边。 第一行包含一个整数 #cf_span[|S|]（#cf_span[1 ≤ |S| ≤ 1000]）——树 #cf_span[S] 的顶点数。 接下来 #cf_span[|S| - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ |S|]），描述树 #cf_span[S] 的边。 下一行包含一个整数 #cf_span[|T|]（#cf_span[1 ≤ |T| ≤ 12]）——树 #cf_span[T] 的顶点数。 接下来 #cf_span[|T| - 1] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ |T|]），描述树 #cf_span[T] 的边。 第一行输出一个整数——该任务的答案对 #cf_span[109 + 7] 取模的结果。 ## Input 第一行包含一个整数 #cf_span[|S|]（#cf_span[1 ≤ |S| ≤ 1000]）——树 #cf_span[S] 的顶点数。接下来 #cf_span[|S| - 1] 行，每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ |S|]），描述树 #cf_span[S] 的边。下一行包含一个整数 #cf_span[|T|]（#cf_span[1 ≤ |T| ≤ 12]）——树 #cf_span[T] 的顶点数。接下来 #cf_span[|T| - 1] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ |T|]），描述树 #cf_span[T] 的边。 ## Output 第一行输出一个整数——该任务的答案对 #cf_span[109 + 7] 取模的结果。 [samples]
**Definitions** Let $ S = (V_S, E_S) $ be a tree with $ |V_S| = n $, $ n \leq 1000 $. Let $ T = (V_T, E_T) $ be a tree with $ |V_T| = m $, $ m \leq 12 $. **Constraints** 1. $ 1 \leq n \leq 1000 $ 2. $ 1 \leq m \leq 12 $ 3. $ S $ and $ T $ are connected, undirected, and acyclic. **Objective** Count the number of subtrees $ S' = (V', E') $ of $ S $ (i.e., connected, acyclic subgraphs of $ S $) such that $ S' \cong T $, i.e., there exists a bijection $ f: V' \to V_T $ satisfying: $$ \{u, v\} \in E' \iff \{f(u), f(v)\} \in E_T $$ Output the count modulo $ 10^9 + 7 $. Two subtrees are distinct if their vertex sets differ.
Samples
Input #1
5
1 2
2 3
3 4
4 5
3
1 2
2 3
Output #1
3
Input #2
3
2 3
3 1
3
1 2
1 3
Output #2
1
Input #3
7
1 2
1 3
1 4
1 5
1 6
1 7
4
4 1
4 2
4 3
Output #3
20
Input #4
5
1 2
2 3
3 4
4 5
4
4 1
4 2
4 3
Output #4
0
API Response (JSON) 
{
  "problem": {
    "name": "F. Tree nesting",
    "description": {
      "content": "You are given two trees (connected undirected acyclic graphs) _S_ and _T_. Count the number of subtrees (connected subgraphs) of _S_ that are isomorphic to tree _T_. Since this number can get quite l",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF762F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two trees (connected undirected acyclic graphs) _S_ and _T_.\n\nCount the number of subtrees (connected subgraphs) of _S_ that are isomorphic to tree _T_. Since this number can get quite l...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定两棵树（连通无向无环图）#cf_span[S] 和 #cf_span[T]。\n\n计算树 #cf_span[S] 中与树 #cf_span[T] 同构的子树（连通子图）的数量。由于这个数可能很大，请输出其对 #cf_span[109 + 7] 取模的结果。\n\n树 #cf_span[S] 的两个子树被认为是不同的，当且仅当存在一个顶点属于其中一个子树但不属于另一个。\n\n树 #cf_span[G] ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S = (V_S, E_S) $ be a tree with $ |V_S| = n $, $ n \\leq 1000 $.  \nLet $ T = (V_T, E_T) $ be a tree with $ |V_T| = m $, $ m \\leq 12 $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac