import sys input = sys.stdin.readline from collections import deque N = int(input()) X = [[] for i in range(N)] for i in range(N-1): x, y = map(int, input().split()) x, y = x-1, y-1 X[x].append(y) X[y].append(x) MI = [min(x) for x in X] MA = [max(x) for x in X] MA2 = [max([y for y in x + [-1] if y != ma]) for x, ma in zip(X, MA)] if False: print("MI =", MI) print("MA =", MA) print("MA2 =", MA2) P = [-1] * N Q = deque([0]) R = [] while Q: i = deque.popleft(Q) R.append(i) for a in X[i]: if a != P[i]: P[a] = i X[a].remove(i) deque.append(Q, a) ##### Settings unit = 0 merge = lambda a, b: a + b ## ↓ この2つは必ず対称的にする(じゃないとバグる) adj_bu = lambda a, i: a * inv(SIZE[i]) % mod adj_td = lambda a, i, p: a * inv(N-SIZE[i]) % mod # SIZEのときはi、それ以外の頂点情報のときはpを使う def adj_bu(a, i, p): if a >= 4: return 4 if a == 0 and p == MI[i]: return 0 if a == 3 and p != MA[i]: return 4 if i == MA[p] or i == MI[p]: return 2 if i == MA2[p]: return 3 return 4 def adj_td(a, i, p): return adj_bu(a, p, i) adj_fin = lambda a, i: "Yes" if a <= 2 else "No" ##### if False: nn = 200200 fa = [1] * (nn+1) fainv = [1] * (nn+1) for i in range(nn): fa[i+1] = fa[i] * (i+1) % mod fainv[-1] = pow(fa[-1], mod-2, mod) for i in range(nn)[::-1]: fainv[i] = fainv[i+1] * (i+1) % mod inv = lambda i: fainv[i] * fa[i-1] % mod print("fa =", fa[:20]) print("fainv =", fainv[:20]) if False: SIZE = [1] * N for i in R[1:][::-1]: SIZE[P[i]] += SIZE[i] print("SIZE =", SIZE) # Size of subtree ME = [unit] * N XX = [0] * N TD = [unit] * N for i in R[1:][::-1]: p = P[i] XX[i] = adj_bu(ME[i], i, p) #################### ME[p] = merge(ME[p], XX[i]) XX[R[0]] = adj_fin(ME[R[0]], R[0]) if False: print("ME =", ME) # Merge before adj print("XX =", XX) # Bottom-up after adj for i in R: ac = TD[i] for j in X[i]: TD[j] = ac ac = merge(ac, XX[j]) ac = unit for j in X[i][::-1]: TD[j] = adj_td(merge(TD[j], ac), j, i) ac = merge(ac, XX[j]) XX[j] = adj_fin(merge(ME[j], TD[j]), j) if False: print("TD =", TD) # Top-down after adj print("XX =", XX) # Final Result print("\n".join(XX))