import sys
sys.setrecursionlimit(200000)
def depth_first(h, p, t, ls, memo):
memo[h] = t - len(ls[h])
memo[h] += 0 if p == 0 else 1
for elem in ls[h]:
if elem == p:
continue
depth_first(elem, h, t, ls, memo)
if memo[elem] < 0:
memo[h] += memo[elem]
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())
ls[f].append(s)
ls[s].append(f)
s = 0
e = n
while s < e:
m = (s + e)//2
t = m
depth_first(1, 0, t, ls, memo)
if memo[1] < 0:
s = m + 1
else:
e = m
print(s)
if __name__ == "__main__":
main()
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
3428 KB |
Output is correct |
2 |
Correct |
24 ms |
3440 KB |
Output is correct |
3 |
Correct |
24 ms |
3492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
3492 KB |
Output is correct |
2 |
Correct |
25 ms |
3492 KB |
Output is correct |
3 |
Correct |
24 ms |
3492 KB |
Output is correct |
4 |
Correct |
24 ms |
3492 KB |
Output is correct |
5 |
Correct |
25 ms |
3704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
3704 KB |
Output is correct |
2 |
Correct |
25 ms |
3704 KB |
Output is correct |
3 |
Correct |
25 ms |
3704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
3728 KB |
Output is correct |
2 |
Correct |
35 ms |
4000 KB |
Output is correct |
3 |
Correct |
34 ms |
4000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
170 ms |
5704 KB |
Output is correct |
2 |
Correct |
217 ms |
9748 KB |
Output is correct |
3 |
Correct |
157 ms |
9748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
590 ms |
10624 KB |
Output is correct |
2 |
Correct |
962 ms |
26432 KB |
Output is correct |
3 |
Correct |
504 ms |
26432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2060 ms |
26432 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2064 ms |
47224 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2068 ms |
68364 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2060 ms |
68364 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |