Many Easy Problems

AtCoder

IDagc005_f

Time5000ms

Memory256MB

Difficulty—

#nck { width: 30px; height: auto; }One day, Takahashi was given the following problem from Aoki: * You are given a tree with $N$ vertices and an integer $K$. The vertices are numbered $1$ through $N$. The edges are represented by pairs of integers $(a_i, b_i)$. * For a set $S$ of vertices in the tree, let $f(S)$ be the minimum number of the vertices in a subtree of the given tree that contains all vertices in $S$. * There are ![image](https://atcoder.jp/img/agc005/ea29e9345ef75e7d965febb790a5aad1.png) ways to choose $K$ vertices from the trees. For each of them, let $S$ be the set of the chosen vertices, and find the sum of $f(S)$ over all ![image](https://atcoder.jp/img/agc005/ea29e9345ef75e7d965febb790a5aad1.png) ways. * Since the answer may be extremely large, print it modulo $924844033$(prime). Since it was too easy for him, he decided to solve this problem for all $K = 1,2,...,N$. ## Constraints * $2 ≦ N ≦ 200,000$ * $1 ≦ a_i, b_i ≦ N$ * The given graph is a tree. ## Input The input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_{N-1}$ $b_{N-1}$ [samples]

Samples

Input #1

3
1 2
2 3

Output #1

3
7
3

![image](https://atcoder.jp/img/agc005/44e2fd5d5e0fe66d1d238ee502639e4e.png)
The diagram above illustrates the case where $K=2$. The chosen vertices are colored pink, and the subtrees with the minimum number of vertices are enclosed by red lines.

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Many Easy Problems",
    "description": {
      "content": "#nck { width: 30px; height: auto; }One day, Takahashi was given the following problem from Aoki: *   You are given a tree with $N$ vertices and an integer $K$. The vertices are numbered $1$ through $",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc005_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "#nck { width: 30px; height: auto; }One day, Takahashi was given the following problem from Aoki:\n\n*   You are given a tree with $N$ vertices and an integer $K$. The vertices are numbered $1$ through $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments