Submission #63062150

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys, heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)
cand_flag = [False] * n
for i in range(n):
    if len(g[i]) >= 4:
        cand_flag[i] = True
if not any(cand_flag):
    print(-1)
    sys.exit(0)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys, heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

cand_flag = [False] * n
for i in range(n):
    if len(g[i]) >= 4:
        cand_flag[i] = True
if not any(cand_flag):
    print(-1)
    sys.exit(0)


H = {i: [] for i in range(n) if cand_flag[i]}
for i in H:
    for j in g[i]:
        if cand_flag[j]:
            H[i].append(j)


down = {}

def dfs_down(v, parent):
    child_vals = []
    for w in H[v]:
        if w == parent:
            continue
        child_vals.append(dfs_down(w, v))
    limit = 4 if parent is None else 3

    best = heapq.nlargest(limit, child_vals)
    res = 1 + sum(best)
    down[v] = res
    return res


def dfs_reroot(v, parent, up_val):
    limit = 4 if parent is None else 3
    cur_list = []
    if up_val is not None:
        cur_list.append(up_val)
    for w in H[v]:
        if w == parent:
            continue
        cur_list.append(down[w])
    cur_dp = 1 + sum(heapq.nlargest(limit, cur_list))
    best = cur_dp
    for w in H[v]:
        if w == parent:
            continue
        temp = []
        if up_val is not None:
            temp.append(up_val)
        for x in H[v]:
            if x == parent or x == w:
                continue
            temp.append(down[x])
        new_up = 1 + sum(heapq.nlargest(3, temp))
        best = max(best, dfs_reroot(w, v, new_up))
    return best

visited = set()
ans_m = 0
for v in H:
    if v in visited:
        continue
    comp = []
    stack = [v]
    while stack:
        cur = stack.pop()
        if cur in visited:
            continue
        visited.add(cur)
        comp.append(cur)
        for w in H[cur]:
            if w not in visited:
                stack.append(w)
    r = comp[0]
    dfs_down(r, None)
    comp_best = dfs_reroot(r, None, None)
    ans_m = max(ans_m, comp_best)

print(3 * ans_m + 2)

Submission Info

Judge Result