https://codeforces.com/problemset/problem/1914/F
Code của em:
from collections import deque
t = int(input())
for __ in range(t):
n = int(input())
arr = [int(_) for _ in input().split(' ')]
children = {}
for i in range(len(arr)):
if arr[i] not in children:
children[arr[i]] = [i + 2]
else:
children[arr[i]].append(i + 2)
q = deque()
q.append((1, 0))
currentDepth = 0
depths = []
while len(q) != 0:
id, depth = q.popleft()
if depth > currentDepth:
depths.append(len(q) + 1)
currentDepth = depth # new depth
for child in children.get(id, []):
q.append((child, depth + 1))
countOne = 0
countOdd = 0
for i in range(len(depths) - 1, -1, -1):
if depths[i] == 1:
countOne += 1
elif depths[i] % 2 == 1:
if countOne == 0:
countOdd += 1
else:
countOne -= 1
elif depths[i] % 2 == 0:
available = min(depths[i] - 1, countOne)
countOne = (countOne - available + (0 if (depths[i] - available) % 2 == 0 else 1))
#print("->", end="")
print(int((n - 1 - countOne - countOdd % 2) / 2))
Em đã thử dùng code trong tutorial để kiểm tra test case. Kết quả là đúng cả 400 test mỗi lần nhấn chạy @@.
from collections import deque
import copy
import random
import sys
def generateTestCase():
n = random.randint(200, 1000)
arr = list(range(2, n + 1))
inputArr = [0] * (n - 1)
q = deque()
q.append(1)
while len(arr) != 0:
id = q.popleft()
if len(q) > 1:
childCount = random.randint(0, min(4, len(arr)))
else:
childCount = random.randint(1, min(4, len(arr)))
for i in range(0, childCount):
q.append(arr[i])
inputArr[arr[i] - 2] = id
arr = arr[childCount:]
return n, inputArr
N = 222222
sz = [0] * N
g = [[] for _ in range(N)]
def init(v):
sz[v] = 1
for u in g[v]:
init(u)
sz[v] += sz[u]
def calc(v, k):
tot = 0
mx = -1
for u in g[v]:
tot += sz[u]
if mx == -1 or sz[mx] < sz[u]:
mx = u
if tot == 0:
return 0
if sz[mx] - k <= tot - sz[mx]:
return (tot - k) // 2
add = tot - sz[mx]
return add + calc(mx, max(0, k + add - 1))
def solve(inputArr):
n = len(inputArr) + 1
for i in range(n):
g[i].clear()
for i in range(1, n):
p = inputArr[i - 1]
g[p - 1].append(i)
init(0)
return calc(0, 0)
def algo(arr):
n = len(arr) + 1
children = {}
for i in range(len(arr)):
if arr[i] not in children:
children[arr[i]] = [i + 2]
else:
children[arr[i]].append(i + 2)
q = deque()
q.append((1, 0))
currentDepth = 0
depths = []
while len(q) != 0:
id, depth = q.popleft()
if depth > currentDepth:
depths.append(len(q) + 1)
currentDepth = depth # new depth
for child in children.get(id, []):
q.append((child, depth + 1))
countOne = 0
countOdd = 0
for i in range(len(depths) - 1, -1, -1):
if depths[i] == 1:
countOne += 1
elif depths[i] % 2 == 1:
if countOne == 0:
countOdd += 1
else:
countOne -= 1
elif depths[i] % 2 == 0:
available = min(depths[i] - 1, countOne)
countOne = (countOne - available + (0 if (depths[i] - available) % 2 == 0 else 1))
#print("->", end="")
return int((n - 1 - countOne - countOdd % 2) / 2)
for _ in range(400):
n, inputArr = generateTestCase()
print(f"Answer: {solve(inputArr)}. Yours: {algo(inputArr)}")
if solve(inputArr) != algo(inputArr):
print(inputArr)
break
Vậy đây là một case khá đặc thù, mọi người giúp em gỡ lỗi với. Em không nghĩ nổi ý tưởng em sai ở đâu. Ý tưởng của em như sau:
Vì các node ở cùng một depth luôn bắt cặp được với nhau nên em xét tất cả các depth của cây input(trừ depth 0), lưu tất cả trong một mảng depths rồi chạy từ cuối về đầu để “dp” ra kết quả. Cách dp là gặp 1 thì đếm lên, gặp lẻ thì cố gắng match với các số 1 trước đó(vì nếu ghép tụi trong depth này với nhau như thế nào thì cũng dôi ra 1), gặp chẵn thì cũng cố gắng match với 1(match với 1 trước rồi mới đi match tụi trong depth với nhau).
Cuối cùng, lấy số depth odd ra tìm dư(vì tụi này luôn dôi ra 1 nên “ghép được với nhau”) và số depth 1 phần tử không bị triệt tiêu trừ ra khỏi (n - 1) rồi chia 2. Sở dĩ, (n - 1) là vì gốc 1 của cây không tham gia ghép cặp.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?