結果

問題 No.1769 Don't Stop the Game
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:24:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,924 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 76,980 KB
最終ジャッジ日時 2025-05-14 13:26:00
合計ジャッジ時間 6,674 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections
import sys

# For fast I/O
input = sys.stdin.readline

def solve():
    N = int(input())
    
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        u -= 1 # 0-indexed
        v -= 1 # 0-indexed
        adj[u].append((v, w))
        adj[v].append((u, w))

    # Constraints: 2 <= N <= 2 * 10^5
    # If N were 0 or 1, we would print 0, but N >= 2.

    val = [-1] * N 
    
    # Compute val[u] = XOR sum from root (node 0) to u
    # Root arbitrarily at node 0. val[0] = 0.
    # Using BFS for val computation.
    q_val_comp = collections.deque()
    q_val_comp.append((0, 0, -1)) # (node, current_xor_from_root, parent)
    val[0] = 0
    
    while q_val_comp:
        curr, current_xor_to_curr, p = q_val_comp.popleft()
        
        for neighbor, weight_edge in adj[curr]:
            if neighbor == p:
                continue
            val[neighbor] = current_xor_to_curr ^ weight_edge
            q_val_comp.append((neighbor, val[neighbor], curr))

    total_valid_pairs = 0

    for i in range(N): # i is the start_node of the pair (i,j)
        val_i = val[i] # The XOR value of the start_node relative to the root (vertex 0)
        
        # BFS queue for paths starting from i
        # Stores (current_node_in_path, parent_of_current_node_in_path)
        q_bfs = collections.deque()
        
        # Initial step: consider direct neighbors of i
        for neighbor_of_i, _ in adj[i]:
            # Condition: XOR sum of path i -> neighbor_of_i must not be 0.
            # Path XOR sum (i -> neighbor_of_i) = val[i] ^ val[neighbor_of_i].
            # This must not be 0, so val[neighbor_of_i] != val[i].
            if val[neighbor_of_i] != val_i:
                total_valid_pairs += 1
                q_bfs.append((neighbor_of_i, i)) 
            # If val[neighbor_of_i] == val_i, this path is immediately invalid.
        
        # Continue BFS for longer paths
        while q_bfs:
            curr_path_node, prev_path_node = q_bfs.popleft()
            
            for neighbor_of_curr, _ in adj[curr_path_node]:
                if neighbor_of_curr == prev_path_node: # Don't go back along the path
                    continue
                
                # Path is i -> ... -> prev_path_node -> curr_path_node -> neighbor_of_curr
                # The XOR sum for the prefix ending at neighbor_of_curr is val[i] ^ val[neighbor_of_curr].
                # This must be non-zero for the path to be valid up to this point.
                # So, val[neighbor_of_curr] must not be equal to val[i].
                if val[neighbor_of_curr] != val_i:
                    total_valid_pairs += 1
                    q_bfs.append((neighbor_of_curr, curr_path_node))
                # If val[neighbor_of_curr] == val_i, this path (and extensions) is invalid. Stop this branch.
    
    print(total_valid_pairs)

solve()
0