Submission #63058140

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n=int(input())
g=[[]for _ in range(n)]
for _ in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
start=-1
for i in range(n):
    if len(g[i])>=4:
        start=i;break
if start==-1:
    exit(print(start))
import sys
sys.setrecursionlimit(10**6)
visited=set()
def dfs(now,prev=-1):
    cnt=[]
    visited.add(now)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

n=int(input())
g=[[]for _ in range(n)]
for _ in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

start=-1
for i in range(n):
    if len(g[i])>=4:
        start=i;break
if start==-1:
    exit(print(start))
import sys
sys.setrecursionlimit(10**6)
visited=set()
def dfs(now,prev=-1):
    cnt=[]
    visited.add(now)
    for v in g[now]:
        if len(g[v])<4:continue
        if v==prev:continue
        cnt.append(dfs(v,now))
    res=1
    cnt.sort(reverse=True)
    for i in range(min(len(cnt),3+int(prev==-1))):
        res+=cnt[i]
    return res
m=1
for start in range(n):
    if len(g[start])>=4 and start not in visited:
        m=max(m,dfs(start))
print(3*m+2)

Submission Info

Judge Result