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 = [[]] * (n+1)
memo = [0] * (n+1)
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 |
320 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
328 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
335 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
316 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
334 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
413 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
632 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
971 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1313 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1298 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |