MEX Tree (Codeforces 1527D)
Tags: Math, trees

You are given a tree with $$$n$$$ nodes, numerated from $$$0$$$ to $$$n-1$$$. For each $$$k$$$ between $$$0$$$ and $$$n$$$, inclusive, you have to count the number of unordered pairs $$$(u,v)$$$, $$$u \neq v$$$, such that the MEX of all the node labels in the shortest path from $$$u$$$ to $$$v$$$ (including end points) is $$$k$$$.The MEX of a sequence of integers is the smallest non-negative integer that does not belong to the sequence.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$).The next $$$n-1$$$ lines of each test case describe the tree that has to be constructed. These lines contain two integers $$$u$$$ and $$$v$$$ ($$$0 \le u,v \le n-1$$$) denoting an edge between $$$u$$$ and $$$v$$$ ($$$u \neq v$$$).It is guaranteed that the given edges form a tree.It is also guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output: For each test case, print $$$n+1$$$ integers: the number of paths in the tree, such that the MEX of all the node labels in that path is $$$k$$$ for each $$$k$$$ from $$$0$$$ to $$$n$$$.

Note:   In example case $$$1$$$,    For $$$k = 0$$$, there is $$$1$$$ path that is from $$$2$$$ to $$$3$$$ as $$$MEX([2, 3]) = 0$$$.  For $$$k = 1$$$, there are $$$2$$$ paths that is from $$$0$$$ to $$$2$$$ as $$$MEX([0, 2]) = 1$$$ and $$$0$$$ to $$$3$$$ as $$$MEX([0, 2, 3]) = 1$$$.  For $$$k = 2$$$, there is $$$1$$$ path that is from $$$0$$$ to $$$1$$$ as $$$MEX([0, 1]) = 2$$$.  For $$$k = 3$$$, there is $$$1$$$ path that is from $$$1$$$ to $$$2$$$ as $$$MEX([1, 0, 2]) = 3$$$  For $$$k = 4$$$, there is $$$1$$$ path that is from $$$1$$$ to $$$3$$$ as $$$MEX([1, 0, 2, 3]) = 4$$$.   In example case $$$2$$$,    For $$$k = 0$$$, there are no such paths.  For $$$k = 1$$$, there are no such paths.  For $$$k = 2$$$, there is $$$1$$$ path that is from $$$0$$$ to $$$1$$$ as $$$MEX([0, 1]) = 2$$$.  

Sample Inputs:
2
4
0 1
0 2
2 3
2
1 0

Sample Outputs:
1 2 1 1 1 
0 0 1

Solution (Python):
from bisect import bisect, bisect_left
from collections import *
from heapq import *
from math import gcd, ceil, sqrt, floor, inf
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def A(n):
    return [0] * n

def AI(n, x):
    return [x] * n

def A2(n, m):
    return [[0] * m for i in range(n)]

def G(n):
    return [[] for i in range(n)]

def GP(it):
    return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
    if mod:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr) % mod)
    else:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr))
    return farr[x]

def ifact(x, mod):
    global ifa
    fact(x, mod)
    ifa.append(pow(farr[-1], mod - 2, mod))
    for i in range(x, 0, -1):
        ifa.append(ifa[-1] * i % mod)
    ifa.reverse()

def per(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return fact(i) // fact(i - j)
    return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return per(i, j) // fact(j)
    return per(i, j, mod) * ifa[j] % mod

def catalan(n):
    return com(2 * n, n) // (n + 1)

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def floorsum(a, b, c, n):
    if a == 0:
        return b // c * (n + 1)
    if a >= c or b >= c:
        return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
    m = (a * n + b) // c
    return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
    a %= m
    if a <= 1:
        return a
    return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
    return n & -n

class BIT:

    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr) - 1

    def update(self, x, v):
        while x <= self.n:
            self.arr[x] += v
            x += x & -x

    def query(self, x):
        ans = 0
        while x:
            ans += self.arr[x]
            x &= x - 1
        return ans

class ST:

    def __init__(self, arr):
        n = len(arr)
        mx = n.bit_length()
        self.st = [[0] * mx for i in range(n)]
        for i in range(n):
            self.st[i][0] = arr[i]
        for j in range(1, mx):
            for i in range(n - (1 << j) + 1):
                self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

    def query(self, l, r):
        if l > r:
            return -inf
        s = (r + 1 - l).bit_length() - 1
        return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

    def __init__(self, n):
        self.c = [-1] * n

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def find(self, x):
        if self.c[x] < 0:
            return x
        self.c[x] = self.find(self.c[x])
        return self.c[x]

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if u == v:
            return False
        if self.c[u] > self.c[v]:
            (u, v) = (v, u)
        self.c[u] += self.c[v]
        self.c[v] = u
        return True

    def size(self, x):
        return -self.c[self.find(x)]

class UFS:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv

class UF:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n
        self.size = AI(n, 1)
        self.edge = A(n)

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            self.edge[pu] += 1
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            self.edge[pu] += self.edge[pv] + 1
            self.size[pu] += self.size[pv]
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv
            self.edge[pv] += self.edge[pu] + 1
            self.size[pv] += self.size[pu]

def Prime(n):
    c = 0
    prime = []
    flag = [0] * (n + 1)
    for i in range(2, n + 1):
        if not flag[i]:
            prime.append(i)
            c += 1
        for j in range(c):
            if i * prime[j] > n:
                break
            flag[i * prime[j]] = prime[j]
            if i % prime[j] == 0:
                break
    return prime

def dij(s, graph):
    d = AI(n, inf)
    d[s] = 0
    heap = [(0, s)]
    vis = A(n)
    while heap:
        (dis, u) = heappop(heap)
        if vis[u]:
            continue
        vis[u] = 1
        for (v, w) in graph[u]:
            if d[v] > d[u] + w:
                d[v] = d[u] + w
                heappush(heap, (d[v], v))
    return d

def bell(s, g):
    dis = AI(n, inf)
    dis[s] = 0
    for i in range(n - 1):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
    change = A(n)
    for i in range(n):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                change[v] = 1
    return dis

def lcm(a, b):
    return a * b // gcd(a, b)

def lis(nums):
    res = []
    for k in nums:
        i = bisect.bisect_left(res, k)
        if i == len(res):
            res.append(k)
        else:
            res[i] = k
    return len(res)

def RP(nums):
    n = len(nums)
    s = set(nums)
    d = {}
    for (i, k) in enumerate(sorted(s), 1):
        d[k] = i
    bi = BIT([0] * (len(s) + 1))
    ans = 0
    for i in range(n - 1, -1, -1):
        ans += bi.query(d[nums[i]] - 1)
        bi.update(d[nums[i]], 1)
    return ans

class DLN:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None

def nb(i, j, n, m):
    for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < n and 0 <= nj < m:
            yield (ni, nj)

def topo(n):
    q = deque()
    res = []
    for i in range(1, n + 1):
        if ind[i] == 0:
            q.append(i)
            res.append(i)
    while q:
        u = q.popleft()
        for v in g[u]:
            ind[v] -= 1
            if ind[v] == 0:
                q.append(v)
                res.append(v)
    return res

@bootstrap
def gdfs(r, p):
    for ch in g[r]:
        if ch != p:
            yield gdfs(ch, r)
    yield None

@bootstrap
def dfs(r, p):
    par[r] = p
    for ch in g[r]:
        if ch != p:
            yield dfs(ch, r)
            cnt[r] += cnt[ch]
    yield None
t = N()
for i in range(t):
    n = N()
    g = G(n)
    ans = A(n + 1)
    for i in range(n - 1):
        (u, v) = RL()
        g[u].append(v)
        g[v].append(u)
    par = A(n)
    cnt = AI(n, 1)
    dfs(0, -1)
    vis = A(n)
    vis[0] = 1
    for v in g[0]:
        ans[0] += cnt[v] * (cnt[v] - 1) // 2
    u = 1
    while par[u]:
        vis[u] = 1
        u = par[u]
    vis[u] = 1
    k = n - cnt[1]
    ans[1] = n * (n - 1) // 2 - ans[0] - cnt[1] * (n - cnt[u])
    l = 0
    lc = n - cnt[u]
    rc = cnt[1]
    r = 1
    f = True
    for i in range(2, n):
        if vis[i]:
            continue
        u = i
        while not vis[u]:
            vis[u] = 1
            u = par[u]
        if u == l:
            ans[i] = (lc - cnt[i]) * rc
            l = i
            lc = cnt[l]
        elif u == r:
            ans[i] = (rc - cnt[i]) * lc
            r = i
            rc = cnt[r]
        else:
            ans[i] = lc * rc
            f = False
            break
    if f:
        ans[-1] = 1
    print(*ans)
''

Solution (Python):
from bisect import bisect, bisect_left
from collections import *
from heapq import *
from math import gcd, ceil, sqrt, floor, inf
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def A(n):
    return [0] * n

def AI(n, x):
    return [x] * n

def A2(n, m):
    return [[0] * m for i in range(n)]

def G(n):
    return [[] for i in range(n)]

def GP(it):
    return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
    if mod:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr) % mod)
    else:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr))
    return farr[x]

def ifact(x, mod):
    global ifa
    fact(x, mod)
    ifa.append(pow(farr[-1], mod - 2, mod))
    for i in range(x, 0, -1):
        ifa.append(ifa[-1] * i % mod)
    ifa.reverse()

def per(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return fact(i) // fact(i - j)
    return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return per(i, j) // fact(j)
    return per(i, j, mod) * ifa[j] % mod

def catalan(n):
    return com(2 * n, n) // (n + 1)

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def floorsum(a, b, c, n):
    if a == 0:
        return b // c * (n + 1)
    if a >= c or b >= c:
        return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
    m = (a * n + b) // c
    return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
    a %= m
    if a <= 1:
        return a
    return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
    return n & -n

class BIT:

    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr) - 1

    def update(self, x, v):
        while x <= self.n:
            self.arr[x] += v
            x += x & -x

    def query(self, x):
        ans = 0
        while x:
            ans += self.arr[x]
            x &= x - 1
        return ans

class ST:

    def __init__(self, arr):
        n = len(arr)
        mx = n.bit_length()
        self.st = [[0] * mx for i in range(n)]
        for i in range(n):
            self.st[i][0] = arr[i]
        for j in range(1, mx):
            for i in range(n - (1 << j) + 1):
                self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

    def query(self, l, r):
        if l > r:
            return -inf
        s = (r + 1 - l).bit_length() - 1
        return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

    def __init__(self, n):
        self.c = [-1] * n

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def find(self, x):
        if self.c[x] < 0:
            return x
        self.c[x] = self.find(self.c[x])
        return self.c[x]

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if u == v:
            return False
        if self.c[u] > self.c[v]:
            (u, v) = (v, u)
        self.c[u] += self.c[v]
        self.c[v] = u
        return True

    def size(self, x):
        return -self.c[self.find(x)]

class UFS:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv

class UF:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n
        self.size = AI(n, 1)
        self.edge = A(n)

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            self.edge[pu] += 1
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            self.edge[pu] += self.edge[pv] + 1
            self.size[pu] += self.size[pv]
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv
            self.edge[pv] += self.edge[pu] + 1
            self.size[pv] += self.size[pu]

def Prime(n):
    c = 0
    prime = []
    flag = [0] * (n + 1)
    for i in range(2, n + 1):
        if not flag[i]:
            prime.append(i)
            c += 1
        for j in range(c):
            if i * prime[j] > n:
                break
            flag[i * prime[j]] = prime[j]
            if i % prime[j] == 0:
                break
    return prime

def dij(s, graph):
    d = AI(n, inf)
    d[s] = 0
    heap = [(0, s)]
    vis = A(n)
    while heap:
        (dis, u) = heappop(heap)
        if vis[u]:
            continue
        vis[u] = 1
        for (v, w) in graph[u]:
            if d[v] > d[u] + w:
                d[v] = d[u] + w
                heappush(heap, (d[v], v))
    return d

def bell(s, g):
    dis = AI(n, inf)
    dis[s] = 0
    for i in range(n - 1):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
    change = A(n)
    for i in range(n):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                change[v] = 1
    return dis

def lcm(a, b):
    return a * b // gcd(a, b)

def lis(nums):
    res = []
    for k in nums:
        i = bisect.bisect_left(res, k)
        if i == len(res):
            res.append(k)
        else:
            res[i] = k
    return len(res)

def RP(nums):
    n = len(nums)
    s = set(nums)
    d = {}
    for (i, k) in enumerate(sorted(s), 1):
        d[k] = i
    bi = BIT([0] * (len(s) + 1))
    ans = 0
    for i in range(n - 1, -1, -1):
        ans += bi.query(d[nums[i]] - 1)
        bi.update(d[nums[i]], 1)
    return ans

class DLN:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None

def nb(i, j, n, m):
    for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < n and 0 <= nj < m:
            yield (ni, nj)

def topo(n):
    q = deque()
    res = []
    for i in range(1, n + 1):
        if ind[i] == 0:
            q.append(i)
            res.append(i)
    while q:
        u = q.popleft()
        for v in g[u]:
            ind[v] -= 1
            if ind[v] == 0:
                q.append(v)
                res.append(v)
    return res

@bootstrap
def gdfs(r, p):
    for ch in g[r]:
        if ch != p:
            yield gdfs(ch, r)
    yield None

@bootstrap
def dfs(r, p):
    par[r] = p
    for ch in g[r]:
        if ch != p:
            yield dfs(ch, r)
            cnt[r] += cnt[ch]
    yield None
t = N()
for i in range(t):
    n = N()
    g = G(n)
    ans = A(n + 1)
    for i in range(n - 1):
        (u, v) = RL()
        g[u].append(v)
        g[v].append(u)
    par = A(n)
    cnt = AI(n, 1)
    dfs(0, -1)
    vis = A(n)
    vis[0] = 1
    for v in g[0]:
        ans[0] += cnt[v] * (cnt[v] - 1) // 2
    u = 1
    while par[u]:
        vis[u] = 1
        u = par[u]
    vis[u] = 1
    k = n - cnt[1]
    ans[1] = n * (n - 1) // 2 - ans[0] - cnt[1] * (n - cnt[u])
    l = 0
    lc = n - cnt[u]
    rc = cnt[1]
    r = 1
    f = True
    for i in range(2, n):
        if vis[i]:
            continue
        u = i
        while not vis[u]:
            vis[u] = 1
            u = par[u]
        if u == l:
            ans[i] = (lc - cnt[i]) * rc
            l = i
            lc = cnt[l]
        elif u == r:
            ans[i] = (rc - cnt[i]) * lc
            r = i
            rc = cnt[r]
        else:
            ans[i] = lc * rc
            f = False
            break
    if f:
        ans[-1] = 1
    print(*ans)
''

Solution (Python):
from collections import deque
import sys
input = sys.stdin.buffer.readline

def bfs(s):
    q = deque()
    q.append(s)
    visit = [0] * n
    visit[s] = 1
    parent = [-1] * n
    p = []
    while q:
        i = q.popleft()
        for j in G[i]:
            if not visit[j]:
                visit[j] = 1
                q.append(j)
                parent[j] = i
                p.append(j)
    return (parent, p)
t = int(input())
for _ in range(t):
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = map(int, input().split())
        G[u].append(v)
        G[v].append(u)
    (parent, p) = bfs(0)
    cnt = [1] * n
    while p:
        i = p.pop()
        cnt[parent[i]] += cnt[i]
    ans = [0] * (n + 1)
    for i in G[0]:
        ans[0] += cnt[i] * (cnt[i] - 1) // 2
    visit = [0] * n
    i = 1
    visit[i] = 1
    while parent[i] ^ -1:
        x = i
        i = parent[i]
        visit[i] = 1
    cnt[0] -= cnt[x]
    (l, r) = ([-1] * n, [-1] * n)
    (l[1], r[1]) = (0, 1)
    m = n
    for i in range(2, n):
        if visit[i]:
            (l[i], r[i]) = (l[i - 1], r[i - 1])
            continue
        j = i
        while not visit[j]:
            visit[j] = 1
            j = parent[j]
        if l[i - 1] == j:
            (l[i], r[i]) = (i, r[i - 1])
        elif r[i - 1] == j:
            (l[i], r[i]) = (l[i - 1], i)
        else:
            m = i
            break
    c = 0
    for i in range(m, 1, -1):
        ans[i] = cnt[l[i - 1]] * cnt[r[i - 1]] - c
        c += ans[i]
    ans[1] = n * (n - 1) // 2 - sum(ans)
    print(*ans)