K. King's Colors

Codeforces

IDCF10193K

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Far, far away, there is the mystical Kingdom of Trees (more formally, "Royal Commonwealth of Connected Undirected Simple Acyclic Graphs"). The King there is very sad because his kingdom is not accepted as a sovereign state in the United Nations. In order to become a member, he needs to make a flag the UN can put on their website. The flag will of course consist of the King's favorite tree, which contains $n$ nodes. The King would be happy to just have the tree colored in black and white, but for the sake of his wife the Queen, he decided that the tree will contain all the favorite colors of their $k$ children (they all have distinct favorite colors). Clearly, no two neighboring nodes can have the same color, but otherwise any coloring of the tree using exactly the $k$ colors would make a feasible flag candidate. How many different flags are possible? The first line contains two integers $n$ and $k$ ($2 <= k <= n <= 2 thin 500$), where $n$ is the number of nodes in the King's favorite tree and $k$ is the number of children. Then follow $n -1$ lines describing the edges in the tree; the $i$'th of these lines contains a non-negative integer $p_i < i$, meaning that node $p_i$ is the parent of $i$. The nodes are numbered from $0$ to $n -1$ and the tree is rooted at node $0$. Note that the embedding of the tree on the flag is already fixed, the only thing that remains is to assign colors. Output the number of different possible color assignments. The number can be quite big, so the King has requested to know the answer modulo $1 thin 000 thin 000 thin 007$. ## Input The first line contains two integers $n$ and $k$ ($2 <= k <= n <= 2 thin 500$), where $n$ is the number of nodes in the King's favorite tree and $k$ is the number of children. Then follow $n -1$ lines describing the edges in the tree; the $i$'th of these lines contains a non-negative integer $p_i < i$, meaning that node $p_i$ is the parent of $i$.The nodes are numbered from $0$ to $n -1$ and the tree is rooted at node $0$. Note that the embedding of the tree on the flag is already fixed, the only thing that remains is to assign colors. ## Output Output the number of different possible color assignments. The number can be quite big, so the King has requested to know the answer modulo $1 thin 000 thin 000 thin 007$. [samples]

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 2 \leq k \leq n \leq 2500 $. Let $ T = (V, E) $ be a rooted tree with $ |V| = n $, nodes labeled $ \{0, 1, \dots, n-1\} $, rooted at node $ 0 $, and $ |E| = n-1 $. Let $ C = \{1, 2, \dots, k\} $ be the set of $ k $ distinct colors. **Constraints** 1. The tree structure is given via parent pointers: for each $ i \in \{1, \dots, n-1\} $, node $ i $ has parent $ p_i $ with $ 0 \leq p_i < i $. 2. A valid coloring is a function $ f: V \to C $ such that for every edge $ (u,v) \in E $, $ f(u) \ne f(v) $. 3. Exactly $ k $ colors must be used (surjective onto $ C $). **Objective** Compute the number of surjective proper colorings of $ T $ using exactly $ k $ colors, modulo $ 1000000007 $. That is, compute: $$ \left| \left\{ f: V \to C \,\middle|\, \forall (u,v) \in E,\, f(u) \ne f(v) \text{ and } \text{image}(f) = C \right\} \right| \mod 1000000007 $$

API Response (JSON)

{
  "problem": {
    "name": "K. King's Colors",
    "description": {
      "content": "Far, far away, there is the mystical Kingdom of Trees (more formally, \"Royal Commonwealth of Connected Undirected Simple Acyclic Graphs\"). The King there is very sad because his kingdom is not accepte",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10193K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Far, far away, there is the mystical Kingdom of Trees (more formally, \"Royal Commonwealth of Connected Undirected Simple Acyclic Graphs\"). The King there is very sad because his kingdom is not accepte...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq k \\leq n \\leq 2500 $.  \nLet $ T = (V, E) $ be a rooted tree with $ |V| = n $, nodes labeled $ \\{0, 1, \\dots, n-1\\} $, rooted at node $ 0 $, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments