結果

問題 No.1796 木上のクーロン
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:48:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,303 bytes
コンパイル時間 244 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 109,336 KB
最終ジャッジ日時 2025-06-12 16:50:03
合計ジャッジ時間 16,218 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, 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)
    
    # 预计算k0 = (N!)^2 mod MOD
    factorial = [1] * (N+1)
    for i in range(1, N+1):
        factorial[i] = factorial[i-1] * i % MOD
    k0 = factorial[N] * factorial[N] % MOD
    
    # 处理每个节点p的贡献
    # 我们需要计算sum_{i} Q_i / (d(p,i)+1)^2
    # 这里采用广度优先搜索来计算每个节点p的贡献
    # 但是这会导致O(N^2)的时间复杂度，无法通过
    # 因此，我们需要寻找更高效的解决方案，例如利用树的性质和数学变换
    # 这里提供一个示例代码，但可能无法通过所有测试用例

    # 示例代码：直接计算每个节点的总和（无法通过N=2e5的情况）
    # 仅作为参考
    
    # 预计算每个节点的层次结构，使用BFS
    # 但是这将导致O(N^2)的时间复杂度，无法处理N=2e5的情况
    # 所以，这里仅提供一个示例代码，无法通过大测试用例
    
    # 预计算每个节点到其他节点的距离，这将导致O(N^2)的空间复杂度
    # 无法处理N=2e5的情况
    # 这里仅作为示例
    
    # 由于时间限制，这里无法提供一个完整的、高效的解决方案
    # 需要进一步的分析和优化
    
    # 以下代码仅用于示例，无法通过大测试用例
    for p in range(1, N+1):
        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)
        total = 0
        for i in range(1, N+1):
            d = dist[i]
            denominator = (d + 1) ** 2
            inv_denominator = pow(denominator, MOD-2, MOD)
            term = Q[i-1] * inv_denominator % MOD
            total = (total + term) % MOD
        E_p = total * k0 % MOD
        print(E_p)
    
if __name__ == "__main__":
    main()
0