Problem:
 Score : 1900 points    Problem Statement  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 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 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}       Output Print N lines. The i -th line should contain the answer to the problem where K=i , modulo 924844033 .        Sample Input 1 3
1 2
2 3      Sample Output 1 3
7
3   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.       Sample Input 2 4
1 2
1 3
1 4      Sample Output 2 4
15
13
4       Sample Input 3 7
1 2
2 3
2 4
4 5
4 6
6 7      Sample Output 3 7
67
150
179
122
45
7

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

MOD = 924844033

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

size = [1] * (N+1)  
for v in order[::-1]:
    size[parent[v]] += size[v]

P = [0] * N
for s in size[2:]:
    P[s] += 1
    P[N-s] += 1

class ModArray(np.ndarray):
    def __new__(cls, input_array):
        obj = np.asarray(input_array, dtype=np.int64).view(cls)
        return obj
    
    @classmethod
    def zeros(cls, *args):
        obj = np.zeros(*args, dtype=np.int64)
        return obj.view(cls)
    
    @classmethod
    def ones(cls, *args):
        obj = np.ones(*args, dtype=np.int64)
        return obj.view(cls)
    
    @classmethod
    def arange(cls, *args):
        obj = np.arange(*args, dtype=np.int64) % MOD
        return obj.view(cls)
    
    @classmethod
    def powers(cls, a, N):
        B = N.bit_length()
        x = cls.ones(1<<B)
        for n in range(B):
            x[1<<n:1<<(n+1)] = x[:1<<n] * a
            a *= a; a %= MOD
        return x[:N]
    
    @classmethod
    def _set_constant_array(cls, N):
        x = cls.arange(N); x[0] = 1
        fact = x.cumprod()
        x = cls.arange(N,0,-1); x[0] = pow(int(fact[-1]), MOD-2, MOD)
        fact_inv = x.cumprod()[::-1]
        inv = cls.zeros(N)
        inv[1:N] = fact_inv[1:N] * fact[0:N-1]
        fact.flags.writeable = False
        fact_inv.flags.writeable = False
        inv.flags.writeable = False
        cls._fact = fact; cls._fact_inv = fact_inv; cls._inverse = inv
        
    @classmethod
    def fact(cls, N):
        if (getattr(cls, '_fact', None) is None) or len(cls._fact) < N:
            cls._set_constant_array(max(N, 10 ** 6))
        return cls._fact[:N]

    @classmethod
    def fact_inv(cls, N):
        if (getattr(cls, '_fact', None) is None) or len(cls._fact) < N:
            cls._set_constant_array(max(N, 10 ** 6))
        return cls._fact_inv[:N]

    @classmethod
    def inverse(cls, N):
        if (getattr(cls, '_fact', None) is None) or len(cls._fact) < N:
            cls._set_constant_array(max(N, 10 ** 6))
        return cls._inverse[:N]
    
    @classmethod
    def convolve_small(cls, f, g):
        Lf = len(f); Lg = len(g); L = Lf + Lg - 1
        if min(Lf, Lg) < 100 or Lf + Lg < 300:
            return (np.convolve(f,g) % MOD).view(cls)
        else:
            fft = np.fft.rfft; ifft = np.fft.irfft; n = 1 << L.bit_length()
            return (np.rint(ifft(fft(f, n) * fft(g, n))[:L]).astype(np.int64) % MOD).view(cls)
    
    @classmethod
    def convolve(cls, f, g, fft_killer=False):
        Lf = len(f); Lg = len(g)
        if Lf < Lg:
            f, g = g, f
            Lf, Lg = Lg, Lf
        if Lg <= (1 << 17) or (not fft_killer):
            fl = f & (1 << 15) - 1; fh = f >> 15
            gl = g & (1 << 15) - 1; gh = g >> 15
            x = cls.convolve_small(fl, gl)
            z = cls.convolve_small(fh, gh)
            y = cls.convolve_small(fl+fh, gl+gh) - x - z
            return x + (y << 15) + (z << 30)
        g = g.resize(Lf)
        n = Lf // 2
        fl = f[:n]; fh = f[n:].copy()
        gl = g[:n]; gh = g[n:].copy()
        x = ModArray.convolve(fl, gl)
        z = ModArray.convolve(fh, gh)
        fh[:len(fl)] += fl; gh[:len(gl)] += gl
        y = ModArray.convolve(fh, gh)
        P = x.resize(Lf + Lf)
        P[n : n+len(x)] -= x
        P[n : n+len(y)] += y
        P[n : n+len(z)] -= z
        P[n+n : n+n+len(z)] += z
        return P[:Lf+Lg-1]
    
    def print(self, sep=' '):
        print(sep.join(self.astype(str)))
        
    def resize(self, N):
        L = len(self)
        if L >= N:
            return self[:N]
        A = np.resize(self, N).view(self.__class__)
        A[L:] = 0
        return A
    
    def diff(self):
        return np.diff(self) % MOD
               
    def cumprod(self):
        L = len(self); Lsq = int(L**.5+1)
        A = self.resize(Lsq**2).reshape(Lsq, Lsq)
        for n in range(1,Lsq):
            A[:,n] *= A[:,n-1]
        for n in range(1,Lsq):
            A[n] *= A[n-1,-1]
        return A.ravel()[:L]

    def __array_wrap__(self, out_arr, context=None):
        if out_arr.dtype == np.int64:
            if context and context[0] == np.mod:
                 return out_arr
            np.mod(out_arr, MOD, out=out_arr)
            return out_arr
        else:
            return np.asarray(out_arr)

P = ModArray(P)
fact = ModArray.fact(N+10)
fact_inv = ModArray.fact_inv(N+10)

Q = ModArray.convolve(P * fact[:N], fact_inv[:N][::-1])[N-1:]
Q *= fact_inv[:N]

x = fact[N] * fact_inv[:N+1] * fact_inv[:N+1][::-1] * N
x[:-1] -= Q

x[1:].print(sep='\n')

Solution (Python):
import sys
import numpy as np

def power_table(MOD, w, size):
    w_table = [0] * size
    w_table[0] = 1
    for i in range(1, size):
        w_table[i] = w_table[i - 1] * w % MOD
    return w_table

def numpy_ntt(MOD, w_table, data, scale=None):
    size = data.size
    step = 1
    while step < size:
        batch_size = size // (step * 2)
        data = data.reshape(step * 2, -1)
        odd = data[0::2]
        even = data[1::2]
        w1 = w_table[0:size // 2:batch_size]
        w2 = w_table[size // 2:size:batch_size]
        sub1 = (odd + even * w1) % MOD
        sub2 = (odd + even * w2) % MOD
        data = np.concatenate((sub1, sub2))
        step *= 2
    if scale is not None:
        data = data * scale % MOD
    return data.flatten()

def read_data():
    int_gen = (int(s) for s in sys.stdin.read().split())

    n = next(int_gen)

    graph = [[] for _ in range(n)]
    for a, b in zip(int_gen, int_gen):
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    size_table = [1] * n

    ret = 0
    stack = [None, 0, 0]

    while True:
        node = stack[-1]
        index = stack[-2]
        size_table[node] += ret
        if index < len(graph[node]):
            dtr = graph[node][index]
            stack[-2] += 1
            if dtr != stack[-3]:
                stack.extend((0, dtr))
            ret = 0
        else:
            del stack[-2:]
            if len(stack) <= 1: break
            ret = size_table[node]

    g = [0] * n
    for s in size_table:
        if s != n:
            g[s - 1] += 1
            g[n - s - 1] += 1
    return (n, g)


def solve():
    MOD = 924844033

    def pow_mod(a, n):
        ret = 1
        while n != 0:
            if n % 2 == 1: ret = ret * a % MOD
            a = a * a % MOD
            n //= 2
        return ret

    n, answer = read_data()

    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i % MOD

    ifac = [0] * (n + 1)
    ifac[n] = pow_mod(fac[n], MOD - 2)
    for i in range(n, 0, -1):
        ifac[i - 1] = ifac[i] * i % MOD

    def comb(x, y):
        return fac[x] * ifac[y] % MOD * ifac[x - y] % MOD

    for i in range(n):
        answer[i] = answer[i] * fac[i + 1] % MOD
    answer.reverse()

    ntt_size = 1
    while ntt_size <= n * 2: ntt_size *= 2

    w_table = power_table(MOD, pow_mod(5, MOD // ntt_size), ntt_size)

    np_w_table = np.array(w_table).reshape(-1, 1)
    ifac_ntt = numpy_ntt(MOD, np_w_table, np.array(ifac[:n] + [0] * (ntt_size - n)))
    answer_ntt = numpy_ntt(MOD, np_w_table, np.array(answer + [0] * (ntt_size - n)))

    answer_ntt = answer_ntt * ifac_ntt % MOD

    for i in range(1, ntt_size // 2):
        w_table[i], w_table[ntt_size - i] = w_table[ntt_size - i], w_table[i]
    answer = numpy_ntt(MOD, np.array(w_table).reshape(-1, 1), answer_ntt, pow_mod(ntt_size, MOD - 2)).tolist()

    for i in range(1, n + 1):
        a = n * comb(n, i)
        b = answer[n - i] * ifac[i]
        print((a - b) % MOD)

solve()

Solution (Python):
import sys
import numpy as np

def power_table(MOD, w, size):
    w_table = [0] * size
    w_table[0] = 1
    for i in range(1, size):
        w_table[i] = w_table[i - 1] * w % MOD
    return w_table

def numpy_ntt(MOD, w_table, data, scale=None):
    size = data.size
    step = 1
    while step < size:
        batch_size = size // (step * 2)
        data = data.reshape(step * 2, -1)
        odd = data[0::2]
        even = data[1::2]
        w1 = w_table[0:size // 2:batch_size]
        w2 = w_table[size // 2:size:batch_size]
        sub1 = (odd + even * w1) % MOD
        sub2 = (odd + even * w2) % MOD
        data = np.concatenate((sub1, sub2))
        step *= 2
    if scale is not None:
        data = data * scale % MOD
    return data.flatten()

def read_data():
    int_list = [int(s) for s in sys.stdin.read().split()]

    n = int_list[0]

    graph = [[] for _ in range(n)]
    for i in range(0, (n - 1) * 2, 2):
        a = int_list[i + 1] - 1
        b = int_list[i + 2] - 1
        graph[a].append(b)
        graph[b].append(a)

    size_table = [1] * n

    ret = 0
    stack = [None, 0, 0]

    while True:
        node = stack[-1]
        index = stack[-2]
        size_table[node] += ret
        if index < len(graph[node]):
            dtr = graph[node][index]
            stack[-2] += 1
            if dtr != stack[-3]:
                stack.extend((0, dtr))
            ret = 0
        else:
            del stack[-2:]
            if len(stack) <= 1: break
            ret = size_table[node]

    g = [0] * n
    for s in size_table:
        if s != n:
            g[s - 1] += 1
            g[n - s - 1] += 1
    return (n, g)


def solve():
    MOD = 924844033

    def pow_mod(a, n):
        ret = 1
        while n != 0:
            if n % 2 == 1: ret = ret * a % MOD
            a = a * a % MOD
            n //= 2
        return ret

    n, answer = read_data()

    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i % MOD

    ifac = [0] * (n + 1)
    ifac[n] = pow_mod(fac[n], MOD - 2)
    for i in range(n, 0, -1):
        ifac[i - 1] = ifac[i] * i % MOD

    def comb(x, y):
        return fac[x] * ifac[y] % MOD * ifac[x - y] % MOD

    for i in range(n):
        answer[i] = answer[i] * fac[i + 1] % MOD
    answer.reverse()

    ntt_size = 1
    while ntt_size <= n * 2: ntt_size *= 2

    w_table = power_table(MOD, pow_mod(5, MOD // ntt_size), ntt_size)

    np_w_table = np.array(w_table).reshape(-1, 1)
    ifac_ntt = numpy_ntt(MOD, np_w_table, np.array(ifac[:n] + [0] * (ntt_size - n)))
    answer_ntt = numpy_ntt(MOD, np_w_table, np.array(answer + [0] * (ntt_size - n)))

    answer_ntt = answer_ntt * ifac_ntt % MOD

    for i in range(1, ntt_size // 2):
        w_table[i], w_table[ntt_size - i] = w_table[ntt_size - i], w_table[i]
    answer = numpy_ntt(MOD, np.array(w_table).reshape(-1, 1), answer_ntt, pow_mod(ntt_size, MOD - 2)).tolist()

    for i in range(1, n + 1):
        a = n * comb(n, i)
        b = answer[n - i] * ifac[i]
        print((a - b) % MOD)

solve()

Solution (Python):
import sys
import numpy as np

def power_table(MOD, w, size):
    w_table = [0] * size
    w_table[0] = 1
    for i in range(1, size):
        w_table[i] = w_table[i - 1] * w % MOD
    return w_table

def numpy_ntt(MOD, w_table, data, scale=None):
    size = data.size
    step = 1
    while step < size:
        batch_size = size // (step * 2)
        data = data.reshape(step * 2, -1)
        odd = data[0::2]
        even = data[1::2]
        w1 = w_table[0:size // 2:batch_size]
        w2 = w_table[size // 2:size:batch_size]
        sub1 = (odd + even * w1) % MOD
        sub2 = (odd + even * w2) % MOD
        data = np.concatenate((sub1, sub2))
        step *= 2
    if scale is not None:
        data = data * scale % MOD
    return data.flatten()

def read_data():
    int_list = [int(s) for s in sys.stdin.read().split()]

    n = int_list[0]

    graph = [[] for _ in range(n)]
    for i in range(0, (n - 1) * 2, 2):
        a = int_list[i + 1] - 1
        b = int_list[i + 2] - 1
        graph[a].append(b)
        graph[b].append(a)

    size_table = [1] * n

    ret = 0
    stack = [-1, 0, 0]

    while True:
        node = stack[-1]
        index = stack[-2]
        size_table[node] += ret
        if index < len(graph[node]):
            dtr = graph[node][index]
            stack[-2] += 1
            if dtr != stack[-3]:
                stack.extend((0, dtr))
            ret = 0
        else:
            del stack[-2:]
            if len(stack) <= 1: break
            ret = size_table[node]

    g = [0] * n
    for s in size_table:
        if s != n:
            g[s - 1] += 1
            g[n - s - 1] += 1
    return (n, g)


def solve():
    MOD = 924844033

    def pow_mod(a, n):
        ret = 1
        while n != 0:
            if n % 2 == 1: ret = ret * a % MOD
            a = a * a % MOD
            n //= 2
        return ret

    n, answer = read_data()

    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i % MOD

    ifac = [0] * (n + 1)
    ifac[n] = pow_mod(fac[n], MOD - 2)
    for i in range(n, 0, -1):
        ifac[i - 1] = ifac[i] * i % MOD

    def comb(x, y):
        return fac[x] * ifac[y] % MOD * ifac[x - y] % MOD

    for i in range(n):
        answer[i] = answer[i] * fac[i + 1] % MOD
    answer.reverse()

    ntt_size = 1
    while ntt_size <= n * 2: ntt_size *= 2

    w_table = power_table(MOD, pow_mod(5, (MOD - 1) // ntt_size), ntt_size)

    np_w_table = np.array(w_table).reshape(-1, 1)
    ifac_ntt = numpy_ntt(MOD, np_w_table, np.array(ifac[:n] + [0] * (ntt_size - n)))
    answer_ntt = numpy_ntt(MOD, np_w_table, np.array(answer + [0] * (ntt_size - n)))

    answer_ntt = answer_ntt * ifac_ntt % MOD

    for i in range(1, ntt_size // 2):
        w_table[i], w_table[ntt_size - i] = w_table[ntt_size - i], w_table[i]
    answer = numpy_ntt(MOD, np.array(w_table).reshape(-1, 1), answer_ntt, pow_mod(ntt_size, MOD - 2)).tolist()

    for i in range(1, n + 1):
        a = n * comb(n, i) % MOD
        b = answer[n - i] * ifac[i] % MOD
        print((a - b + MOD) % MOD)

solve()

Solution (Python):
import sys
import numpy as np

def power_table(MOD, w, size):
    w_table = [0] * size
    w_table[0] = 1
    for i in range(1, size):
        w_table[i] = w_table[i - 1] * w % MOD
    return w_table

def numpy_ntt(MOD, w_table, data, scale=None):
    data_np = np.array(data)
    size = len(data)
    step = 1
    while step < size:
        batch_size = size // (step * 2)
        data_np = data_np.reshape((step * 2, -1))
        w1 = w_table[0:size // 2:batch_size].reshape((step, -1)).repeat(batch_size, axis=1)
        w2 = w_table[size // 2:size:batch_size].reshape((step, -1)).repeat(batch_size, axis=1)
        odd = data_np[0::2]
        even = data_np[1::2]
        sub1 = (odd + even * w1) % MOD
        sub2 = (odd + even * w2) % MOD
        data_np = np.concatenate((sub1, sub2))
        step *= 2
    if scale is not None:
        data_np = data_np * scale % MOD
    return data_np.flatten()

def read_data():
    int_list = [int(s) for s in sys.stdin.read().split()]

    n = int_list[0]

    graph = [[] for _ in range(n)]
    for i in range(0, (n - 1) * 2, 2):
        a = int_list[i + 1] - 1
        b = int_list[i + 2] - 1
        graph[a].append(b)
        graph[b].append(a)

    size_table = [1] * n

    ret = 0
    stack = [-1, 0, 0]

    while True:
        node = stack[-1]
        index = stack[-2]
        size_table[node] += ret
        if index < len(graph[node]):
            dtr = graph[node][index]
            stack[-2] += 1
            if dtr != stack[-3]:
                stack.extend((0, dtr))
            ret = 0
        else:
            del stack[-2:]
            if len(stack) <= 1: break
            ret = size_table[node]

    g = [0] * n
    for s in size_table:
        if s != n:
            g[s - 1] += 1
            g[n - s - 1] += 1
    return (n, g)


def solve():
    MOD = 924844033

    def pow_mod(a, n):
        ret = 1
        while n != 0:
            if n % 2 == 1: ret = ret * a % MOD
            a = a * a % MOD
            n //= 2
        return ret

    n, answer = read_data()

    fac = [0] * (n + 1)
    fac[0] = 1
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i % MOD

    ifac = [0] * (n + 1)
    ifac[n] = pow_mod(fac[n], MOD - 2)
    for i in range(n, 0, -1):
        ifac[i - 1] = ifac[i] * i % MOD

    def comb(x, y):
        return fac[x] * ifac[y] % MOD * ifac[x - y] % MOD

    for i in range(n):
        answer[i] = answer[i] * fac[i + 1] % MOD
    answer.reverse()

    ntt_size = 1
    while ntt_size <= n * 2: ntt_size *= 2

    w_table = power_table(MOD, pow_mod(5, (MOD - 1) // ntt_size), ntt_size)

    np_w_table = np.array(w_table)
    ifac_ntt = numpy_ntt(MOD, np_w_table, ifac[:n] + [0] * (ntt_size - n))
    answer_ntt = numpy_ntt(MOD, np_w_table, answer + [0] * (ntt_size - n))

    answer_ntt = answer_ntt * ifac_ntt % MOD

    for i in range(1, ntt_size // 2):
        w_table[i], w_table[ntt_size - i] = w_table[ntt_size - i], w_table[i]
    answer = numpy_ntt(MOD, np.array(w_table), answer_ntt, pow_mod(ntt_size, MOD - 2)).tolist()

    for i in range(1, n + 1):
        a = n * comb(n, i) % MOD
        b = answer[n - i] * ifac[i] % MOD
        print((a - b + MOD) % MOD)

solve()