結果

問題 No.2377 SUM AND XOR on Tree
ユーザー titiatitia
提出日時 2023-07-13 04:45:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,401 bytes
コンパイル時間 466 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 296,028 KB
最終ジャッジ日時 2024-09-14 16:51:15
合計ジャッジ時間 50,005 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,224 KB
testcase_01 AC 42 ms
52,736 KB
testcase_02 AC 41 ms
52,096 KB
testcase_03 AC 40 ms
52,480 KB
testcase_04 AC 41 ms
51,968 KB
testcase_05 AC 41 ms
52,352 KB
testcase_06 AC 41 ms
52,352 KB
testcase_07 AC 42 ms
52,352 KB
testcase_08 AC 2,106 ms
296,028 KB
testcase_09 AC 2,130 ms
289,320 KB
testcase_10 AC 2,053 ms
288,996 KB
testcase_11 AC 2,076 ms
294,740 KB
testcase_12 AC 2,177 ms
289,780 KB
testcase_13 AC 2,212 ms
291,588 KB
testcase_14 AC 1,993 ms
279,580 KB
testcase_15 AC 2,100 ms
292,200 KB
testcase_16 AC 2,028 ms
288,872 KB
testcase_17 AC 2,072 ms
289,440 KB
testcase_18 AC 79 ms
71,424 KB
testcase_19 AC 77 ms
70,528 KB
testcase_20 AC 77 ms
70,272 KB
testcase_21 AC 77 ms
71,040 KB
testcase_22 AC 77 ms
70,912 KB
testcase_23 AC 1,921 ms
288,596 KB
testcase_24 AC 2,030 ms
295,264 KB
testcase_25 AC 2,066 ms
288,032 KB
testcase_26 TLE -
testcase_27 AC 3,965 ms
268,920 KB
testcase_28 AC 3,848 ms
261,988 KB
testcase_29 AC 915 ms
284,940 KB
testcase_30 AC 878 ms
282,884 KB
testcase_31 AC 877 ms
280,956 KB
testcase_32 AC 1,490 ms
293,868 KB
testcase_33 AC 1,480 ms
293,744 KB
testcase_34 AC 1,461 ms
293,672 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

    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%mod,b%mod]

            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]

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

print(ANS%mod)
0