結果

問題 No.2377 SUM AND XOR on Tree
ユーザー titiatitia
提出日時 2023-07-13 04:45:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,401 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 86,880 KB
実行使用メモリ 298,596 KB
最終ジャッジ日時 2023-10-12 18:22:33
合計ジャッジ時間 48,353 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,088 KB
testcase_01 AC 75 ms
70,972 KB
testcase_02 AC 73 ms
70,944 KB
testcase_03 AC 71 ms
71,264 KB
testcase_04 AC 72 ms
71,368 KB
testcase_05 AC 72 ms
71,252 KB
testcase_06 AC 73 ms
71,184 KB
testcase_07 AC 72 ms
71,412 KB
testcase_08 AC 2,024 ms
294,340 KB
testcase_09 AC 2,088 ms
289,212 KB
testcase_10 AC 2,195 ms
289,024 KB
testcase_11 AC 2,098 ms
295,316 KB
testcase_12 AC 2,053 ms
289,328 KB
testcase_13 AC 1,993 ms
293,312 KB
testcase_14 AC 1,873 ms
290,480 KB
testcase_15 AC 2,213 ms
292,160 KB
testcase_16 AC 1,969 ms
285,208 KB
testcase_17 AC 2,002 ms
290,504 KB
testcase_18 AC 102 ms
76,876 KB
testcase_19 AC 100 ms
76,828 KB
testcase_20 AC 101 ms
76,812 KB
testcase_21 AC 103 ms
76,528 KB
testcase_22 AC 103 ms
76,680 KB
testcase_23 AC 1,830 ms
289,536 KB
testcase_24 AC 1,877 ms
297,864 KB
testcase_25 AC 2,027 ms
297,656 KB
testcase_26 AC 3,653 ms
265,056 KB
testcase_27 AC 3,727 ms
263,560 KB
testcase_28 TLE -
testcase_29 AC 919 ms
286,604 KB
testcase_30 AC 905 ms
286,520 KB
testcase_31 AC 892 ms
285,224 KB
testcase_32 AC 1,344 ms
298,596 KB
testcase_33 AC 1,370 ms
298,164 KB
testcase_34 AC 1,337 ms
297,328 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