#998122 (PyPy3) No.1976 Cut then Connect

• 問題: No.1976 Cut then Connect
• ユーザー: 已经死了
• 提出日時: 2024-07-27 11:51:24
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 558 ms / 2,000 ms
• コード長: 3,783 bytes
• コンパイル時間: 367 ms
• コンパイル使用メモリ: 82,284 KB
• 実行使用メモリ: 107,148 KB
• 最終ジャッジ日時: 2024-07-27 11:51:38
• 合計ジャッジ時間: 14,139 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 31

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
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=ii()
g=[[] for _ in range(n+1)]
for _ in range(n-1):
    u,v=li()
    g[u]+=[v]
    g[v]+=[u]
h=[0]*(n+1) #i子树中，i所在最长链
d=[0]*(n+1) #i子树直径
@bootstrap
def dfs(u,fa):
    pre=-1
    for v in g[u]:
        if v==fa:
            continue
        yield dfs(v,u)
        d[u]=max(d[u],d[v],pre+h[v]+2)
        pre=max(pre,h[v])
        h[u]=max(h[u],h[v]+1)
    yield None
dfs(1,-1)
#print(d)
global res
res=inf
@bootstrap
def dfs2(u,fa):
    global res
    f1=f2=f3=-1
    d1=d2=0
    for v in g[u]:
        if h[v]>f1:
            f1,f2,f3=h[v],f1,f2
        elif h[v]>f2:
            f2,f3=h[v],f2
        elif h[v]>f3:
            f3=h[v]
        if d[v]>d1:
            d1,d2=d[v],d1
        elif d[v]>d2:
            d2=d[v]
    
    for v in g[u]:
        if v==fa:
            continue
        
        if d1==d[v]:
            nd1=d2
        else:
            nd1=d1
        if f1==h[v]:
            nd1=max(nd1,f2+f3+2)
        elif f2==h[v]:
            nd1=max(nd1,f1+f3+2)
        else:
            nd1=max(nd1,f1+f2+2)
        nd2=d[v]
        
        newd=max((nd1+1)//2+(nd2+1)//2+1,nd1,nd2)
        #print(u,v,nd1,nd2,newd)
        res=min(res,newd)
        d[u]=nd1
        if f1==h[v]:
            h[u]=f2+1
        else:
            h[u]=f1+1
        yield dfs2(v,u)
    yield None
dfs2(1,-1)
print(res)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX