結果

問題 No.1718 Random Squirrel
ユーザー ああいいああいい
提出日時 2022-03-16 19:36:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 481 ms / 2,000 ms
コード長 2,644 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 81,672 KB
実行使用メモリ 120,588 KB
最終ジャッジ日時 2023-10-25 01:14:45
合計ジャッジ時間 9,371 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,396 KB
testcase_01 AC 37 ms
53,396 KB
testcase_02 AC 38 ms
53,396 KB
testcase_03 AC 37 ms
53,396 KB
testcase_04 AC 38 ms
53,396 KB
testcase_05 AC 37 ms
53,396 KB
testcase_06 AC 38 ms
53,396 KB
testcase_07 AC 38 ms
53,396 KB
testcase_08 AC 37 ms
53,396 KB
testcase_09 AC 38 ms
53,396 KB
testcase_10 AC 38 ms
53,396 KB
testcase_11 AC 305 ms
88,200 KB
testcase_12 AC 208 ms
80,604 KB
testcase_13 AC 294 ms
85,380 KB
testcase_14 AC 310 ms
88,804 KB
testcase_15 AC 341 ms
95,420 KB
testcase_16 AC 256 ms
83,836 KB
testcase_17 AC 292 ms
87,776 KB
testcase_18 AC 409 ms
111,220 KB
testcase_19 AC 345 ms
97,824 KB
testcase_20 AC 202 ms
80,960 KB
testcase_21 AC 399 ms
93,220 KB
testcase_22 AC 481 ms
117,432 KB
testcase_23 AC 448 ms
94,004 KB
testcase_24 AC 391 ms
93,152 KB
testcase_25 AC 476 ms
117,960 KB
testcase_26 AC 240 ms
120,588 KB
testcase_27 AC 245 ms
113,148 KB
testcase_28 AC 235 ms
120,332 KB
testcase_29 AC 261 ms
98,652 KB
testcase_30 AC 258 ms
98,652 KB
testcase_31 AC 232 ms
98,652 KB
testcase_32 AC 262 ms
98,652 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:
            if v in s:
                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