C. Helga Hufflepuff's Cup

Codeforces

IDCF855C

Time2000ms

Memory256MB

Difficulty—

dptrees

English · Original

Chinese · Translation

Formal · Original

Harry, Ron and Hermione have figured out that Helga Hufflepuff's cup is a horcrux. Through her encounter with Bellatrix Lestrange, Hermione came to know that the cup is present in Bellatrix's family vault in Gringott's Wizarding Bank. The Wizarding bank is in the form of a tree with total _n_ vaults where each vault has some type, denoted by a number between 1 to _m_. A tree is an undirected connected graph with no cycles. The vaults with the highest security are of type _k_, and all vaults of type _k_ have the highest security. **There can be at most _x_ vaults of highest security**. Also, **if a vault is of the highest security, its adjacent vaults are guaranteed to not be of the highest security and their type is guaranteed to be less than _k_**. Harry wants to consider every possibility so that he can easily find the best path to reach Bellatrix's vault. So, you have to tell him, given the tree structure of Gringotts, the number of possible ways of giving each vault a type such that the above conditions hold. ## Input The first line of input contains two space separated integers, _n_ and _m_ — the number of vaults and the number of different vault types possible. (1 ≤ _n_ ≤ 105, 1 ≤ _m_ ≤ 109). Each of the next _n_ - 1 lines contain two space separated integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_) representing the _i_\-th edge, which shows there is a path between the two vaults _u__i_ and _v__i_. It is guaranteed that the given graph is a tree. The last line of input contains two integers _k_ and _x_ (1 ≤ _k_ ≤ _m_, 1 ≤ _x_ ≤ 10), the type of the highest security vault and the maximum possible number of vaults of highest security. ## Output Output a single integer, the number of ways of giving each vault a type following the conditions modulo 109 + 7. [samples] ## Note In test case 1, we cannot have any vault of the highest security as its type is 1 implying that its adjacent vaults would have to have a vault type less than 1, which is not allowed. Thus, there is only one possible combination, in which all the vaults have type 2.

哈利、罗恩和赫敏已经发现赫尔加·赫奇帕奇的杯子是一个魂器。通过与贝拉特里克斯·莱斯特兰奇的接触，赫敏得知这个杯子位于格里戈维奇巫师银行的贝拉特里克斯家族金库中。巫师银行的结构是一棵树，共有 #cf_span[n] 个金库，每个金库有一种类型，用介于 #cf_span[1] 到 #cf_span[m] 之间的数字表示。树是一种无环的无向连通图。安全性最高的金库类型为 #cf_span[k]，且所有类型为 #cf_span[k] 的金库都具有最高安全性。 *最高安全性的金库数量最多为 #cf_span[x] 个*。此外，*如果一个金库是最高安全性的，那么它的相邻金库一定不是最高安全性，且其类型必须小于 #cf_span[k]*。哈利希望考虑所有可能性，以便找到通往贝拉特里克斯金库的最佳路径。因此，你需要告诉他，在给定格里戈维奇银行树形结构的情况下，有多少种方式为每个金库分配类型，使得上述条件成立。输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m] —— 金库数量和可能的金库类型数量。（#cf_span[1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9]）。接下来的 #cf_span[n - 1] 行每行包含两个用空格分隔的整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]），表示第 #cf_span[i] 条边，表明金库 #cf_span[ui] 和 #cf_span[vi] 之间存在路径。保证给定的图是一棵树。输入的最后一行包含两个整数 #cf_span[k] 和 #cf_span[x]（#cf_span[1 ≤ k ≤ m, 1 ≤ x ≤ 10]），分别表示最高安全性金库的类型和最高安全性金库的最大可能数量。请输出一个整数，表示满足条件的分配方式数量，对 #cf_span[10^9 + 7] 取模。在第一个测试用例中，我们不能有任何最高安全性的金库，因为其类型为 #cf_span[1]，这意味着其相邻金库的类型必须小于 #cf_span[1]，这是不允许的。因此，只有一种可能的组合，即所有金库的类型均为 #cf_span[2]。 ## Input 输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m] —— 金库数量和可能的金库类型数量。（#cf_span[1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9]）。接下来的 #cf_span[n - 1] 行每行包含两个用空格分隔的整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]），表示第 #cf_span[i] 条边，表明金库 #cf_span[ui] 和 #cf_span[vi] 之间存在路径。保证给定的图是一棵树。输入的最后一行包含两个整数 #cf_span[k] 和 #cf_span[x]（#cf_span[1 ≤ k ≤ m, 1 ≤ x ≤ 10]），分别表示最高安全性金库的类型和最高安全性金库的最大可能数量。 ## Output 请输出一个整数，表示满足条件的分配方式数量，对 #cf_span[10^9 + 7] 取模。 [samples] ## Note 在第一个测试用例中，我们不能有任何最高安全性的金库，因为其类型为 #cf_span[1]，这意味着其相邻金库的类型必须小于 #cf_span[1]，这是不允许的。因此，只有一种可能的组合，即所有金库的类型均为 #cf_span[2]。

**Definitions** Let $ n, m, k, x \in \mathbb{Z} $ with $ 1 \leq n \leq 10^5 $, $ 1 \leq m \leq 10^9 $, $ 1 \leq k \leq m $, $ 1 \leq x \leq 10 $. Let $ T = (V, E) $ be a tree with $ |V| = n $ vertices (vaults) and $ |E| = n-1 $ edges. Each vertex $ v \in V $ is assigned a type $ t(v) \in \{1, 2, \dots, m\} $. Let $ S = \{ v \in V \mid t(v) = k \} $ denote the set of highest-security vaults. **Constraints** 1. $ |S| \leq x $ 2. For all $ v \in S $, and for all neighbors $ u \in N(v) $: - $ t(u) \neq k $ - $ 1 \leq t(u) < k $ 3. For all $ v \notin S $: - $ 1 \leq t(v) \leq m $, and if $ t(v) \neq k $, then $ t(v) \in \{1, 2, \dots, m\} \setminus \{k\} $ **Objective** Count the number of valid type assignments $ t: V \to \{1, 2, \dots, m\} $ satisfying the above constraints, modulo $ 10^9 + 7 $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. Helga Hufflepuff's Cup",
    "description": {
      "content": "Harry, Ron and Hermione have figured out that Helga Hufflepuff's cup is a horcrux. Through her encounter with Bellatrix Lestrange, Hermione came to know that the cup is present in Bellatrix's family v",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF855C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Harry, Ron and Hermione have figured out that Helga Hufflepuff's cup is a horcrux. Through her encounter with Bellatrix Lestrange, Hermione came to know that the cup is present in Bellatrix's family v...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "哈利、罗恩和赫敏已经发现赫尔加·赫奇帕奇的杯子是一个魂器。通过与贝拉特里克斯·莱斯特兰奇的接触，赫敏得知这个杯子位于格里戈维奇巫师银行的贝拉特里克斯家族金库中。\n\n巫师银行的结构是一棵树，共有 #cf_span[n] 个金库，每个金库有一种类型，用介于 #cf_span[1] 到 #cf_span[m] 之间的数字表示。树是一种无环的无向连通图。\n\n安全性最高的金库类型为 #cf_span[k]，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, k, x \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq m \\leq 10^9 $, $ 1 \\leq k \\leq m $, $ 1 \\leq x \\leq 10 $.  \nLet $ T = (V, E) $ be a tree with $ |V| = n $ vert...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments