Tree Tree Tree

AtCoder

IDarc167_f

Time5000ms

Memory256MB

Difficulty—

You are given integers $N$ and $K$ such that $2\leq K\leq N$. > **Problem: potato** > We have a weighted rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root. > For each $2\leq i\leq N$, the parent of vertex $i$ is $p_{i}\;(1\leq p_{i}<i)$, and the edge connecting $i$ and $p_{i}$ has a weight of $q_{i-1}$. > Here, $q=(q_{1},q_{2},\dots,q_{N-1})$ is a permutation of $(1,2,\dots,N-1)$. > Let $cost(u,v)$ be the maximum weight of an edge in the simple path connecting vertices $u$ and $v$. > Find $\sum_{u=1}^{N} \sum_{v=u+1}^{N} cost(u,v)$. * * * > **Problem: tomato** > You are given an integer $a$ such that $1\leq a\lt K$. There are $\frac{((N-1)!)^{2}}{K-1}$ possible pairs of $p$ and $q$ in the problem "potato" such that $p_{K}=a$. Find the sum, modulo $998244353$, of the answers to the problem over all those pairs. For each $a=1,\dots,K-1$, find the answer to the problem "tomato". ## Constraints * $2\leq K\leq N\leq 10^{5}$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $K$ [samples]

Samples

Input #1

4 4

Output #1

170
170
172

Input #2

3 2

Output #2

Input #3

16 7

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Tree Tree Tree",
    "description": {
      "content": "You are given integers $N$ and $K$ such that $2\\leq K\\leq N$. > **Problem: potato** > We have a weighted rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root. > For each $2\\leq i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc167_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given integers $N$ and $K$ such that $2\\leq K\\leq N$.\n\n> **Problem: potato**\n> We have a weighted rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root.\n> For each $2\\leq i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments