結果

問題 No.3373 Partial Complement Tree
コンテスト
ユーザー tassei903
提出日時 2025-11-21 21:47:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 569 ms / 2,000 ms
コード長 1,373 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 163,916 KB
最終ジャッジ日時 2025-11-21 21:47:31
合計ジャッジ時間 10,206 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
"""

S = k について

操作したとき 辺の数が 
もともと x だったとき
k * (k + 1) / 2 - 2x
k * (k - 1) = 4x

x < k

k <= 4

(k, x) = (4, 3), (3, )


"""
mod = 998244353
def solve(n, g):
    dp = [[1, 0, 0, 0, 0] for i in range(n)]
    q = [0]
    seen = [0] * n
    seen[0] = 1
    et = []
    par = [-1] * n
    while q:
        x = q.pop()
        et.append(x)
        for y in g[x]:
            if seen[y]:
                continue
            seen[y] = 1
            q.append(y)
            par[y] = x
    ans = 0
    for i in et[::-1]:
        ans += dp[i][3] + dp[i][2] * dp[i][1]
        if par[i] != -1:
            ans -= dp[i][0] * dp[i][1]
            for j in range(4):
                dp[par[i]][j+1] += dp[i][j]
        
        # print(i, dp[i])

    return ans % mod
        

for _ in range(ni()):
    n = ni()
    g = [[]for i in range(n)]
    for _ in range(n-1):
        u, v = na()
        u -= 1
        v -= 1
        g[u].append(v)
        g[v].append(u)
    print(solve(n, g))
0