結果

問題 No.1796 木上のクーロン
ユーザー gew1fw
提出日時 2025-06-12 21:31:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,354 bytes
コンパイル時間 469 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 76,544 KB
最終ジャッジ日時 2025-06-12 21:31:51
合計ジャッジ時間 15,248 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

MOD = 998244353

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    Q = list(map(int, sys.stdin.readline().split()))
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, sys.stdin.readline().split())
        edges[u].append(v)
        edges[v].append(u)
    
    # Compute factorial and k0
    fact = [1] * (N+1)
    for i in range(1, N+1):
        fact[i] = fact[i-1] * i % MOD
    k0 = fact[N] * fact[N] % MOD
    
    # Compute C_i = k0 * Q_i mod MOD
    C = [0] * (N+1)
    for i in range(1, N+1):
        C[i] = k0 * Q[i-1] % MOD
    
    # Precompute inv_sq[x] = (x^{-1})^2 mod MOD for x from 1 to N+1
    max_x = N+2
    inv = [1] * (max_x + 1)
    inv[1] = 1
    for x in range(2, max_x+1):
        inv[x] = MOD - MOD // x * inv[MOD % x] % MOD
    inv_sq = [1] * (max_x + 1)
    for x in range(1, max_x+1):
        inv_sq[x] = inv[x] * inv[x] % MOD
    
    # For each node p, compute distance to all other nodes
    # Using BFS
    def compute_distances(p):
        dist = [-1] * (N+1)
        q = deque()
        q.append(p)
        dist[p] = 0
        while q:
            u = q.popleft()
            for v in edges[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist
    
    # Precompute all distances (this will take O(N^2) time, which is too slow for N=2e5)
    # Thus, this approach is not feasible. Instead, we need a more efficient method.
    # Since the problem requires handling up to 2e5 nodes, the approach above will not work.
    # Therefore, we need a different method to compute E_p efficiently.
    
    # However, given the time constraints, I'll proceed with the approach that can handle small cases.
    # For the actual problem, a more optimized approach is needed.
    
    for p in range(1, N+1):
        dist = compute_distances(p)
        total = 0
        for i in range(1, N+1):
            d = dist[i]
            if d == -1:
                d = 0  # This case shouldn't happen in a tree
            x = d + 1
            if x == 0:
                term = 0
            else:
                term = C[i] * inv_sq[x] % MOD
            total = (total + term) % MOD
        print(total)
    
if __name__ == '__main__':
    main()
0