結果

問題 No.2377 SUM AND XOR on Tree
ユーザー titiatitia
提出日時 2023-07-13 04:44:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,878 ms / 4,000 ms
コード長 1,425 bytes
コンパイル時間 447 ms
コンパイル使用メモリ 86,680 KB
実行使用メモリ 293,568 KB
最終ジャッジ日時 2023-10-12 18:21:39
合計ジャッジ時間 63,908 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,356 KB
testcase_01 AC 74 ms
71,216 KB
testcase_02 AC 72 ms
71,388 KB
testcase_03 AC 73 ms
71,332 KB
testcase_04 AC 73 ms
71,296 KB
testcase_05 AC 73 ms
71,316 KB
testcase_06 AC 72 ms
71,320 KB
testcase_07 AC 72 ms
71,216 KB
testcase_08 AC 2,467 ms
290,580 KB
testcase_09 AC 2,816 ms
282,948 KB
testcase_10 AC 2,375 ms
284,160 KB
testcase_11 AC 2,397 ms
283,156 KB
testcase_12 AC 2,448 ms
281,648 KB
testcase_13 AC 2,517 ms
288,192 KB
testcase_14 AC 2,261 ms
278,460 KB
testcase_15 AC 2,355 ms
290,848 KB
testcase_16 AC 2,296 ms
293,568 KB
testcase_17 AC 2,330 ms
284,056 KB
testcase_18 AC 104 ms
77,332 KB
testcase_19 AC 99 ms
77,104 KB
testcase_20 AC 100 ms
76,524 KB
testcase_21 AC 102 ms
76,560 KB
testcase_22 AC 110 ms
77,064 KB
testcase_23 AC 1,836 ms
289,596 KB
testcase_24 AC 2,012 ms
286,452 KB
testcase_25 AC 2,373 ms
290,872 KB
testcase_26 AC 3,865 ms
265,164 KB
testcase_27 AC 3,841 ms
263,476 KB
testcase_28 AC 3,829 ms
265,424 KB
testcase_29 AC 3,878 ms
277,016 KB
testcase_30 AC 3,610 ms
273,828 KB
testcase_31 AC 3,761 ms
273,448 KB
testcase_32 AC 1,544 ms
290,976 KB
testcase_33 AC 1,549 ms
292,020 KB
testcase_34 AC 1,564 ms
292,080 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