結果

問題 No.1817 Reversed Edges
ユーザー lam6er
提出日時 2025-03-20 21:14:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 323 ms / 2,000 ms
コード長 2,739 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 127,524 KB
最終ジャッジ日時 2025-03-20 21:15:08
合計ジャッジ時間 7,619 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1

    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a = int(input[ptr])
        b = int(input[ptr+1])
        ptr += 2
        edges[a].append(b)
        edges[b].append(a)

    # Build parent and children using BFS
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    q = deque([1])
    parent[1] = 0  # root has no parent

    while q:
        u = q.popleft()
        for v in edges[u]:
            if parent[u] != v and parent[v] == 0:
                parent[v] = u
                children[u].append(v)
                q.append(v)

    # Compute subtree sizes using post-order traversal
    size = [1] * (N + 1)
    stack = [(1, False)]
    while stack:
        node, processed = stack.pop()
        if not processed:
            stack.append((node, True))
            # Push children in reverse order to process them in order
            for child in reversed(children[node]):
                stack.append((child, False))
        else:
            for child in children[node]:
                size[node] += size[child]

    # Compute in_time and out_time using pre-order traversal
    in_time = [0] * (N + 1)
    out_time = [0] * (N + 1)
    time = 0
    stack = [(1, False)]
    while stack:
        node, processed = stack.pop()
        if not processed:
            time += 1
            in_time[node] = time
            stack.append((node, True))
            # Push children in reverse order to process them in correct order
            for child in reversed(children[node]):
                stack.append((child, False))
        else:
            out_time[node] = time

    # Prepare the difference array
    diff = [0] * (N + 2)  # indices 0..N+1
    total = 0

    for u in range(1, N + 1):
        for v in children[u]:
            if u > v:
                total += 1
            delta = 1 if (v > u) else -1
            l = in_time[v]
            r = out_time[v]
            diff[l] += delta
            if r + 1 <= N:
                diff[r + 1] -= delta

    # Compute prefix sums and map back to nodes
    reverse_in_time = [0] * (N + 1)
    for node in range(1, N + 1):
        reverse_in_time[in_time[node]] = node

    current = 0
    prefix = [0] * (N + 1)
    for i in range(1, N + 1):
        current += diff[i]
        node = reverse_in_time[i]
        prefix[node] = current

    # Generate the answer
    answer = [0] * (N + 1)
    for node in range(1, N + 1):
        answer[node] = total + prefix[node]

    for i in range(1, N + 1):
        print(answer[i])

if __name__ == '__main__':
    main()
0