{"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 $N$. The edges are represented by pairs of integers $(a_i, b_i)$.\n*   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$.\n*   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.\n*   Since the answer may be extremely large, print it modulo $924844033$(prime).\n\nSince it was too easy for him, he decided to solve this problem for all $K = 1,2,...,N$.\n\n## Constraints\n\n*   $2 ≦ N ≦ 200,000$\n*   $1 ≦ a_i, b_i ≦ N$\n*   The given graph is a tree.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$:$\n$a_{N-1}$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc005_f","tags":[],"sample_group":[["3\n1 2\n2 3","3\n7\n3\n\n![image](https://atcoder.jp/img/agc005/44e2fd5d5e0fe66d1d238ee502639e4e.png)\nThe 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."],["4\n1 2\n1 3\n1 4","4\n15\n13\n4"],["7\n1 2\n2 3\n2 4\n4 5\n4 6\n6 7","7\n67\n150\n179\n122\n45\n7"]],"created_at":"2026-03-03 11:01:14"}}