結果

問題 No.1718 Random Squirrel
ユーザー ああいいああいい
提出日時 2022-03-16 19:35:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,613 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 81,624 KB
実行使用メモリ 120,012 KB
最終ジャッジ日時 2023-10-25 01:13:07
合計ジャッジ時間 9,646 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,336 KB
testcase_01 AC 38 ms
53,336 KB
testcase_02 AC 38 ms
53,336 KB
testcase_03 WA -
testcase_04 AC 37 ms
53,336 KB
testcase_05 AC 38 ms
53,336 KB
testcase_06 AC 37 ms
53,336 KB
testcase_07 WA -
testcase_08 AC 37 ms
53,336 KB
testcase_09 AC 37 ms
53,336 KB
testcase_10 AC 36 ms
53,336 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 463 ms
117,896 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 260 ms
98,588 KB
testcase_30 AC 257 ms
98,588 KB
testcase_31 AC 232 ms
98,588 KB
testcase_32 AC 261 ms
98,564 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,K = map(int,input().split())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    u,v = map(int,input().split())
    G[u].append(v)
    G[v].append(u)
D = list(map(int,input().split()))
s = set(D)

depth = [0] * (N + 1)
dp = [0] * (N + 1)
stack = [(~1,0),(1,0)]
while stack:
    now,parent = stack.pop()
    if now >= 0:
        for v in G[now]:
            if v == parent:continue
            stack.append((~v,now))
            stack.append((v,now))
    else:
        now = ~now
        for v in G[now]:
            if v == parent:continue
            if depth[v] != 0:
                depth[now] = max(depth[now],depth[v] + 1)
            else:
                if v in s:
                    depth[now] = max(depth[now],1)
            if dp[v] != 0:
                dp[now] += dp[v] + 2
            else:
                if v in s:
                    dp[now] += 2
ans = [0] * (N + 1)
depth2 = [0] * (N +1)
dp2 = [0] * (N + 1)
stack = [(1,0)]
while stack:
    now,parent = stack.pop()
    n = len(G[now])
    hidarid = [0] * (n+1)
    migid = [0] * (n + 1)
    hidaridp = [0] * (n + 1)
    migidp = [0] * (n + 1)
    for i in range(n):
        v = G[now][i]
        hidarid[i+1] = hidarid[i]
        hidaridp[i+1] = hidaridp[i]
        if v == parent:continue
        if depth[v] != 0:
            hidarid[i+1] = max(hidarid[i+1],depth[v]+1)
            hidaridp[i+1] += dp[v] + 2
        else:
            if v in s:
                hidarid[i+1] = max(hidarid[i+1],1)
                hidaridp[i+1] += 2
    for i in reversed(range(n)):
        v = G[now][i]
        migid[i] = migid[i+1]
        migidp[i] = migidp[i+1]
        if v == parent:continue
        if depth[v] != 0:
            migid[i] = max(migid[i],depth[v] + 1)
            migidp[i] += dp[v] + 2
        else:
            migid[i] = max(migid[i],1)
            migidp[i] += 2
    for i in range(n):
        v = G[now][i]
        if v == parent:continue
        tmpd = max(hidarid[i],migid[i+1],depth2[now])
        if depth2[now] == 0:
            if parent in s:
                tmpd = max(tmpd,1)
        tmpdp = hidaridp[i] + migidp[i+1] + dp2[now]
        if dp2[now] == 0:
            if parent in s:
                tmpdp += 2
        if tmpd != 0:
            depth2[v] = tmpd + 1
            dp2[v] = tmpdp + 2
        else:
            if now in s:
                depth2[v] = 1
                dp2[v] = 2
        stack.append((v,now))
    
    ans[now] = hidaridp[-1] + dp2[now] - max(depth2[now],hidarid[-1])
    if dp2[now] == 0:
        if parent in s:
            ans[now] += 2
for i in ans[1:]:
    print(i)
#print(dp,depth)
0