結果

問題 No.1796 木上のクーロン
コンテスト
ユーザー Nachia
提出日時 2021-12-10 01:00:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,285 bytes
コンパイル時間 983 ms
コンパイル使用メモリ 89,712 KB
最終ジャッジ日時 2025-01-26 07:23:02
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 TLE * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/modint>
using namespace std;


struct heavy_light_decomposition{
private:

    int N;
    vector<int> P;
    vector<int> PP;
    vector<int> PD;
    vector<int> D;
    vector<int> I;

    vector<int> rangeL;
    vector<int> rangeR;

public:

    heavy_light_decomposition(const vector<vector<int>>& E = {{}}){
        N = E.size();
        P.assign(N, -1);
        I = {0};
        I.reserve(N);
        for(int i=0; i<I.size(); i++){
            int p = I[i];
            for(int e : E[p]) if(P[p] != e){
                I.push_back(e);
                P[e] = p;
            }
        }
        vector<int> Z(N, 1);
        vector<int> nx(N, -1);
        PP.resize(N);
        for(int i=0; i<N; i++) PP[i] = i;
        for(int i=N-1; i>=1; i--){
            int p = I[i];
            Z[P[p]] += Z[p];
            if(nx[P[p]] == -1) nx[P[p]] = p;
            if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p;
        }

        for(int p : I) if(nx[p] != -1) PP[nx[p]] = p;

        PD.assign(N,N);
        PD[0] = 0;
        D.assign(N,0);
        for(int p : I) if(p != 0){
            PP[p] = PP[PP[p]];
            PD[p] = min(PD[PP[p]], PD[P[p]]+1);
            D[p] = D[P[p]]+1;
        }
        
        rangeL.assign(N,0);
        rangeR.assign(N,0);
        vector<int> dfs;
        dfs.push_back(0);
        while(dfs.size()){
            int p = dfs.back();
            rangeR[p] = rangeL[p] + Z[p];
            int ir = rangeR[p];
            dfs.pop_back();
            for(int e : E[p]) if(P[p] != e) if(e != nx[p]){
                rangeL[e] = (ir -= Z[e]);
                dfs.push_back(e);
            }
            if(nx[p] != -1){
                rangeL[nx[p]] = rangeL[p] + 1;
                dfs.push_back(nx[p]);
            }
        }

        I.resize(N);
        for(int i=0; i<N; i++) I[rangeL[i]] = i;
    }

    int depth(int p) const {
        return D[p];
    }

    int lca(int u, int v) const {
        if(PD[u] < PD[v]) swap(u, v);
        while(PD[u] > PD[v]) u = P[PP[u]];
        while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; }
        return (D[u] > D[v]) ? v : u;
    }

    int dist(int u, int v) const {
        return depth(u) + depth(v) - depth(lca(u,v)) * 2;
    }

    vector<pair<int,int>> path(int r, int c, bool include_root = true, bool reverse_path = false) const {
        vector<pair<int,int>> res;
        while(PD[r] < PD[c]){
            res.push_back({ rangeL[PP[c]], rangeL[c]+1 });
            c = P[PP[c]];
        }
        if(PP[r] != PP[c]) return {};
        if(D[r] > D[c]) return {};
        res.push_back({ rangeL[r], rangeL[c]+1 });
        if(!include_root){
            res.back().first++;
            if(res.back().first == res.back().second) res.pop_back();
        }
        if(!reverse_path) reverse(res.begin(),res.end());
        return move(res);
    }

    const vector<int>& idxs() const {
        return rangeL;
    }

    int meet(int x, int y, int z) const {
        return lca(x,y) ^ lca(y,z) ^ lca(x,z);
    }

    int jump(int from, int to, int d) const {
        int g = lca(from,to);
        int dist0 = D[from] - D[g] * 2 + D[to];
        if(dist0 > d) return -1;
        int p = from;
        if(D[from] - D[g] > d){ p = to; d = dist0 - d; }
        while(D[p] - D[PP[p]] > d){
            d -= D[p] - D[PP[p]] + 1;
            p = P[PP[p]];
        }
        return I[rangeL[p] - d];
    }
};



using m32 = atcoder::modint998244353;


int main() {
    int N; cin >> N;
    vector<m32> Q(N);
    for(int i=0; i<N; i++){ int q; cin >> q; Q[i] = q; }
    vector<vector<int>> E(N);
    for(int i=0; i<N-1; i++){
        int u,v; cin >> u >> v; u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    m32 k0 = 1;
    for(int i=1; i<=N; i++) k0 *= i;
    k0 = k0 * k0;

    auto hld = heavy_light_decomposition(E);
    
    for(int p=0; p<N; p++){
        m32 ans = 0;
        for(int i=0; i<N; i++){
            m32 dist = hld.dist(p,i);
            ans += k0 * Q[i] / ((dist + 1) * (dist + 1));
        }
        cout << ans.val() << "\n";
    }
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0