結果

問題 No.1769 Don't Stop the Game
ユーザー gew1fw
提出日時 2025-06-12 14:20:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,631 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 77,056 KB
最終ジャッジ日時 2025-06-12 14:20:32
合計ジャッジ時間 6,668 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

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)]  # 1-based
    for _ in range(N-1):
        A = int(input[ptr])
        B = int(input[ptr+1])
        C = int(input[ptr+2])
        ptr +=3
        edges[A].append((B, C))
        edges[B].append((A, C))
    
    # Compute X_u for each node using BFS
    X = [0] * (N+1)
    visited = [False] * (N+1)
    from collections import deque
    q = deque()
    root = 1
    q.append(root)
    visited[root] = True
    while q:
        u = q.popleft()
        for v, c in edges[u]:
            if not visited[v]:
                visited[v] = True
                X[v] = X[u] ^ c
                q.append(v)
    
    # Group nodes by their X value
    groups = defaultdict(list)
    for u in range(1, N+1):
        groups[X[u]].append(u)
    
    # For each u, count the number of nodes v where the path u to v does not contain any node w with X[w] == X[u] except u
    total = 0
    for u in range(1, N+1):
        x_u = X[u]
        # Forbidden nodes are all in groups[x_u] except u
        forbidden = groups[x_u]
        forbidden_set = set(forbidden)
        # Find the number of nodes v such that the path u to v does not contain any node in forbidden except u
        # This is equivalent to the number of nodes not in forbidden, plus the nodes in forbidden that can be reached without passing through any forbidden node (only u)
        # This is a bit tricky, but perhaps the subtree can be considered
        # Alternative approach: the count is the number of nodes in the tree not in forbidden, plus the count of nodes in forbidden that are in the subtree of u
        # But this is unclear, so perhaps use another BFS
        # Perform BFS from u and count the nodes reachable without passing through any forbidden node (except u)
        visited_u = [False] * (N+1)
        q = deque()
        q.append(u)
        visited_u[u] = True
        count_u = 0
        while q:
            current = q.popleft()
            count_u += 1
            for v, c in edges[current]:
                if not visited_u[v]:
                    # Check if v is forbidden and not u
                    if v == u:
                        continue
                    if X[v] == x_u:
                        continue
                    visited_u[v] = True
                    q.append(v)
        # Subtract 1 (u itself) and add to total
        total += (count_u - 1)
    
    print(total)

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