結果

問題 No.2377 SUM AND XOR on Tree
ユーザー titiatitia
提出日時 2023-07-13 04:44:16
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,425 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 293,764 KB
最終ジャッジ日時 2024-09-14 16:50:21
合計ジャッジ時間 69,027 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,096 KB
testcase_01 AC 42 ms
52,736 KB
testcase_02 AC 41 ms
52,096 KB
testcase_03 AC 41 ms
52,224 KB
testcase_04 AC 41 ms
52,224 KB
testcase_05 AC 41 ms
52,096 KB
testcase_06 AC 41 ms
52,352 KB
testcase_07 AC 41 ms
52,096 KB
testcase_08 AC 2,624 ms
289,864 KB
testcase_09 AC 2,816 ms
280,960 KB
testcase_10 AC 2,700 ms
282,552 KB
testcase_11 AC 2,740 ms
293,764 KB
testcase_12 AC 2,709 ms
282,476 KB
testcase_13 AC 2,611 ms
279,460 KB
testcase_14 AC 2,447 ms
280,080 KB
testcase_15 AC 2,661 ms
280,672 KB
testcase_16 AC 2,503 ms
280,500 KB
testcase_17 AC 2,593 ms
287,748 KB
testcase_18 AC 85 ms
72,704 KB
testcase_19 AC 82 ms
71,680 KB
testcase_20 AC 80 ms
70,912 KB
testcase_21 AC 83 ms
71,936 KB
testcase_22 AC 90 ms
74,496 KB
testcase_23 AC 2,076 ms
288,728 KB
testcase_24 AC 2,249 ms
285,632 KB
testcase_25 AC 2,682 ms
287,540 KB
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 AC 1,811 ms
288,964 KB
testcase_33 AC 1,777 ms
287,516 KB
testcase_34 AC 1,781 ms
288,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N=int(input())

E=[[] for i in range(N)]

for i in range(N-1):
    x,y=map(int,input().split())
    x-=1
    y-=1
    E[x].append(y)
    E[y].append(x)

A=list(map(int,input().split()))

ROOT=0

QUE=[ROOT] 
Parent=[-1]*N
Parent[ROOT]=N # ROOTの親を定めておく.
Child=[[] for i in range(N)]
TOP_SORT=[] # トポロジカルソート

while QUE: # トポロジカルソートと同時に親を見つける
    x=QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to]==-1:
            Parent[to]=x
            Child[x].append(to)
            QUE.append(to)

ANS=0
mod=998244353

for i in range(30):
    X=[0]*N

    for j in range(N):
        if A[j] & (1<<i) != 0:
            X[j]=1

    #print(X)

    DP=[[0,0] for i in range(N+1)]

    for x in TOP_SORT[::-1]:
        if len(Child[x])==0:
            if X[x]==1:
                DP[x]=[0,1]
            else:
                DP[x]=[1,0]

        else:
            NOW=[-1,-1]
            for c in Child[x]:
                if NOW==[-1,-1]:
                    NOW=DP[c]
                else:
                    b = NOW[0]*DP[c][1] + NOW[1]*DP[c][0]
                    a = NOW[0]*DP[c][0] + NOW[1]*DP[c][1]

                    NOW=[a,b]

            DP[x]=NOW
                    
            if X[x]==1:
                DP[x][0],DP[x][1]=DP[x][1],DP[x][0]

        DP[x][0]+=DP[x][1]


    #print(DP)

    ANS+=DP[0][1]*(1<<i)

print(ANS%mod)
0