import sys
sys.setrecursionlimit(200000)
def depth_first(h, p, t, ls, memo):
sm = 0
for elem in ls[h]:
if elem == p:
continue
depth_first(elem, h, t, ls, memo)
sm += memo[elem]
memo[h] = max(sm - t + 1, 1)
def main():
n = int(input())
ls = [[] for i in range(n + 2)]
memo = [0 for i in range(n + 2)]
for _ in range(n - 1):
f, s = map(int, input().split())
f -= 1
s -= 1
ls[f].append(s)
ls[s].append(f)
s = 0
e = n
while not s > e:
m = (s + e) >> 1
t = m
depth_first(0, -1, t, ls, memo)
if memo[0] > 1:
s = m + 1
else:
e = m-1
print(s)
if __name__ == "__main__":
main()
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
35 ms |
11340 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
32 ms |
11448 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
34 ms |
11664 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
35 ms |
11664 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
42 ms |
13648 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
40 ms |
13908 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
35 ms |
15648 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
44 ms |
17444 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
62 ms |
28508 KB |
Execution failed because the return code was nonzero |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
60 ms |
28584 KB |
Execution failed because the return code was nonzero |
2 |
Halted |
0 ms |
0 KB |
- |