結果

問題 No.1718 Random Squirrel
ユーザー 已经死了已经死了
提出日時 2024-06-27 17:33:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 647 ms / 2,000 ms
コード長 5,662 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 172,252 KB
最終ジャッジ日時 2024-06-27 17:33:55
合計ジャッジ時間 15,507 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 176 ms
92,032 KB
testcase_01 AC 159 ms
92,032 KB
testcase_02 AC 156 ms
92,032 KB
testcase_03 AC 158 ms
92,160 KB
testcase_04 AC 156 ms
92,160 KB
testcase_05 AC 157 ms
92,160 KB
testcase_06 AC 154 ms
92,160 KB
testcase_07 AC 155 ms
92,160 KB
testcase_08 AC 164 ms
92,032 KB
testcase_09 AC 159 ms
92,032 KB
testcase_10 AC 159 ms
92,160 KB
testcase_11 AC 445 ms
104,224 KB
testcase_12 AC 335 ms
95,964 KB
testcase_13 AC 484 ms
101,664 KB
testcase_14 AC 468 ms
104,864 KB
testcase_15 AC 502 ms
107,324 KB
testcase_16 AC 440 ms
100,012 KB
testcase_17 AC 451 ms
103,708 KB
testcase_18 AC 587 ms
116,480 KB
testcase_19 AC 507 ms
106,752 KB
testcase_20 AC 358 ms
98,016 KB
testcase_21 AC 541 ms
109,296 KB
testcase_22 AC 644 ms
120,832 KB
testcase_23 AC 626 ms
110,372 KB
testcase_24 AC 573 ms
109,660 KB
testcase_25 AC 647 ms
120,960 KB
testcase_26 AC 328 ms
107,488 KB
testcase_27 AC 335 ms
107,904 KB
testcase_28 AC 330 ms
107,492 KB
testcase_29 AC 468 ms
171,916 KB
testcase_30 AC 490 ms
172,016 KB
testcase_31 AC 459 ms
172,252 KB
testcase_32 AC 469 ms
172,040 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import os,sys,random,threading
#sys.exit() 退出程序
from random import randint,choice,shuffle
#randint(a,b)从[a,b]范围随机选择一个数
#choice(seq)seq可以是一个列表,元组或字符串,从seq中随机选取一个元素
#shuffle(x)将一个可变的序列x中的元素打乱
from copy import deepcopy
from io import BytesIO,IOBase
from types import GeneratorType
from functools import lru_cache,reduce
#reduce(op,迭代对象)
from bisect import bisect_left,bisect_right
#bisect_left(x) 大于等于x的第一个下标
#bisect_right(x) 大于x的第一个下标
from collections import Counter,defaultdict,deque
from itertools import accumulate,combinations,permutations
#accumulate(a)用a序列生成一个累积迭代器，一般list化前面放个[0]做前缀和用
#combinations(a,k)a序列选k个 组合迭代器
#permutations(a,k)a序列选k个 排列迭代器
from heapq import  heapify,heappop,heappush
#heapify将列表转为堆
from typing import Generic,Iterable,Iterator,TypeVar,Union,List
from string import ascii_lowercase,ascii_uppercase,digits
#小写字母，大写字母，十进制数字
from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf
#ceil向上取整，floor向下取整 ，sqrt开方 ，factorial阶乘
from decimal import Decimal,getcontext
#Decimal(s) 实例化Decimal对象,一般使用字符串
#getcontext().prec=100 修改精度
from sys import stdin, stdout, setrecursionlimit
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
mod = int(1e9 + 7) #998244353
inf = int(1e20)
py = lambda :print("YES")
pn = lambda :print("NO")
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右下左上
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0),(-1, 1)]  # →↘↓↙←↖↑↗



import os,sys,random,threading
#sys.exit() 退出程序
#sys.setrecursionlimit(10**6) #调整栈空间
from random import randint,choice,shuffle
#randint(a,b)从[a,b]范围随机选择一个数
#choice(seq)seq可以是一个列表,元组或字符串,从seq中随机选取一个元素
#shuffle(x)将一个可变的序列x中的元素打乱
from copy import deepcopy
from io import BytesIO,IOBase
from types import GeneratorType
from functools import lru_cache,reduce
#reduce(op,迭代对象)
from bisect import bisect_left,bisect_right
#bisect_left(x) 大于等于x的第一个下标
#bisect_right(x) 大于x的第一个下标
from collections import Counter,defaultdict,deque
from itertools import accumulate,combinations,permutations
#accumulate(a)用a序列生成一个累积迭代器，一般list化前面放个[0]做前缀和用
#combinations(a,k)a序列选k个 组合迭代器
#permutations(a,k)a序列选k个 排列迭代器
from heapq import  heapify,heappop,heappush
#heapify将列表转为堆
from typing import Generic,Iterable,Iterator,TypeVar,Union,List
from string import ascii_lowercase,ascii_uppercase,digits
#小写字母，大写字母，十进制数字
from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf
#ceil向上取整，floor向下取整 ，sqrt开方 ，factorial阶乘
from decimal import Decimal,getcontext
#Decimal(s) 实例化Decimal对象,一般使用字符串
#getcontext().prec=100 修改精度
from sys import stdin, stdout, setrecursionlimit
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
mod = int(1e9 + 7) #998244353
inf = 1<<60
py = lambda :print("YES")
pn = lambda :print("NO")
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右下左上
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0),(-1, 1)]  # →↘↓↙←↖↑↗







def bootstrap(f, stack=[]):   #yield
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

n,m=li()


g=[[] for _ in range(n+1)]

for _ in range(n-1):
    u,v=li()
    g[u]+=[v]
    g[v]+=[u]

vis=[False]*(n+1)

for i in li():
    vis[i]=True

dis=[-inf]*(n+1) 
#1为根时，i离i子树内的最远的鬼的距离
#dis[i]=-inf 表示i子树内没有鬼

f=[0]*(n+1)

@bootstrap
def dfs(u,fa):
    if vis[u]:
        dis[u]=0
    for v in g[u]:
        if v==fa:
            continue
        yield dfs(v,u)
        dis[u]=max(dis[u],dis[v]+1)
        if f[v] or vis[v]:
            f[u]+=f[v]+2
    yield None
dfs(1,-1)

res=[-inf]*(n+1) 
#i为根时，离i点最远的鬼的距离
#print(f)

@bootstrap
def dfs2(u,fa):
    if vis[u]:
        fi=se=0
    else:
        fi=se=-inf
    tot=0
    for v in g[u]:
        if f[v] or vis[v]:
            tot+=f[v]+2
        if dis[v]+1>fi:
            fi,se=dis[v]+1,fi
        elif dis[v]+1>se:
            se=dis[v]+1
    # if u in [1,3,4]:
    #     print(f,u)
    res[u]=tot-fi
    for v in g[u]:
        if v==fa:
            continue
        if fi==dis[v]+1:
            dis[u]=se
        else:
            dis[u]=fi
        if f[v] or vis[v]:
            f[u]=tot-(f[v]+2)
        else:
            f[u]=tot
        # f[u]=tot-int(f[v] or vis[v])*(f[v]+2)
        # if v==3:
        #     print(int(f[v] or vis[v]),(f[v]+2),3,tot,f[u])
        yield dfs2(v,u)
    yield None
dfs2(1,-1)

for i in range(1,n+1):
    print(res[i])
0