結果
| 問題 |
No.1976 Cut then Connect
|
| コンテスト | |
| ユーザー |
 tamato
|
| 提出日時 | 2022-06-10 22:50:57 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,171 bytes |
| コンパイル時間 | 332 ms |
| コンパイル使用メモリ | 82,288 KB |
| 実行使用メモリ | 143,144 KB |
| 最終ジャッジ日時 | 2024-09-21 06:43:37 |
| 合計ジャッジ時間 | 9,291 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 11 WA * 20 |
ソースコード
mod = 998244353
def main():
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
adj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
a, b = map(int, input().split())
adj[a].append(b)
adj[b].append(a)
que = deque()
que.append(1)
seen = [-1] * (N+1)
seen[1] = 0
par = [0] * (N+1)
child = [[] for _ in range(N+1)]
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if seen[u] == -1:
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
v0 = seq[0]
que = deque()
que.append(v0)
seen = [-1] * (N+1)
seen[v0] = 0
par = [0] * (N+1)
child = [[] for _ in range(N+1)]
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if seen[u] == -1:
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
v1 = seq[0]
D = seen[v1]
if D & 1:
v = v1
for _ in range(D // 2):
v = par[v]
vl = v
vr = par[v]
vl_ori = vl
vr_ori = vr
que = deque()
que.append(vl)
seen = [-1] * (N+1)
seen[vl] = 0
par = [0] * (N+1)
child = [[] for _ in range(N+1)]
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if u == vr_ori:
continue
if seen[u] == -1:
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
vl = seq[0]
que = deque()
que.append(vl)
seen = [-1] * (N + 1)
seen[vl] = 0
par = [0] * (N + 1)
child = [[] for _ in range(N + 1)]
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if seen[u] == -1:
if u == vr_ori:
continue
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
dl = seen[seq[0]]
que = deque()
que.append(vr)
seen = [-1] * (N + 1)
seen[vr] = 0
par = [0] * (N + 1)
child = [[] for _ in range(N + 1)]
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if seen[u] == -1:
if u == vl_ori:
continue
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
vr = seq[0]
que = deque()
que.append(vr)
seen = [-1] * (N + 1)
seen[vr] = 0
par = [0] * (N + 1)
child = [[] for _ in range(N + 1)]
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if seen[u] == -1:
if u == vl_ori:
continue
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
dr = seen[seq[0]]
print((dl + 1) // 2 + (dr + 1) // 2 + 1)
else:
ans = N * 2
v = v1
for _ in range(D // 2):
v = par[v]
v0 = v
que = deque()
que.append(v0)
seen = [-1] * (N+1)
seen[v0] = 0
par = [0] * (N+1)
child = [[] for _ in range(N+1)]
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if seen[u] == -1:
seen[u] = seen[v] + 1
par[u] = v
child[v].append(u)
que.append(u)
seq.reverse()
subtree_len = [(0, 0)]
for c in child[v0]:
que = deque()
seq = []
que.append(c)
while que:
v = que.popleft()
for vv in child[v]:
que.append(vv)
seq.append(v)
subtree_len.append((seen[seq[-1]], c))
subtree_len.sort(key=lambda x: x[0], reverse=True)
for c in child[v0]:
cc = c
que = deque()
que.append(cc)
seen = {}
seen[cc] = 0
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if u == v0:
continue
if u not in seen:
seen[u] = seen[v] + 1
que.append(u)
seq.reverse()
cc = seq[0]
que = deque()
que.append(cc)
seen = {}
seen[cc] = 0
seq = []
while que:
v = que.popleft()
seq.append(v)
for u in adj[v]:
if u == v0:
continue
if u not in seen:
seen[u] = seen[v] + 1
que.append(u)
seq.reverse()
dc = seen[seq[0]]
if c == subtree_len[0][1]:
dc2 = subtree_len[1][0] + subtree_len[2][0]
elif c == subtree_len[1][1]:
dc2 = subtree_len[0][0] + subtree_len[2][0]
else:
dc2 = subtree_len[0][0] + subtree_len[1][0]
ans = min(ans, (dc + 1) // 2 + (dc2 + 1) // 2 + 1)
#print(cc, ans, dc, dc2)
print(ans)
#print(subtree_len)
if __name__ == '__main__':
main()