結果

問題 No.1718 Random Squirrel
ユーザー ああいいああいい
提出日時 2022-03-16 19:36:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 448 ms / 2,000 ms
コード長 2,644 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 120,976 KB
最終ジャッジ日時 2024-09-24 20:18:29
合計ジャッジ時間 8,826 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,640 KB
testcase_01 AC 36 ms
53,692 KB
testcase_02 AC 41 ms
54,308 KB
testcase_03 AC 39 ms
53,364 KB
testcase_04 AC 38 ms
54,576 KB
testcase_05 AC 40 ms
53,116 KB
testcase_06 AC 38 ms
53,912 KB
testcase_07 AC 38 ms
53,492 KB
testcase_08 AC 38 ms
53,008 KB
testcase_09 AC 38 ms
52,932 KB
testcase_10 AC 38 ms
52,652 KB
testcase_11 AC 281 ms
88,396 KB
testcase_12 AC 200 ms
81,204 KB
testcase_13 AC 282 ms
86,016 KB
testcase_14 AC 299 ms
89,068 KB
testcase_15 AC 323 ms
96,228 KB
testcase_16 AC 247 ms
84,380 KB
testcase_17 AC 277 ms
88,048 KB
testcase_18 AC 400 ms
111,816 KB
testcase_19 AC 334 ms
98,456 KB
testcase_20 AC 193 ms
81,304 KB
testcase_21 AC 373 ms
93,680 KB
testcase_22 AC 443 ms
118,200 KB
testcase_23 AC 410 ms
94,568 KB
testcase_24 AC 366 ms
93,488 KB
testcase_25 AC 448 ms
118,780 KB
testcase_26 AC 237 ms
120,976 KB
testcase_27 AC 240 ms
113,648 KB
testcase_28 AC 232 ms
120,704 KB
testcase_29 AC 258 ms
99,328 KB
testcase_30 AC 255 ms
99,064 KB
testcase_31 AC 226 ms
99,328 KB
testcase_32 AC 258 ms
99,328 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