結果

問題 No.828 全方位神童数
コンテスト
ユーザー 梧桐
提出日時 2026-02-23 23:40:04
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 200 ms / 2,000 ms
コード長 1,071 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,196 ms
コンパイル使用メモリ 93,792 KB
実行使用メモリ 25,260 KB
最終ジャッジ日時 2026-02-23 23:40:13
合計ジャッジ時間 8,337 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 200010, MOD = 1000000007;

int n, r[N], fa[N], dep[N];
LL ans;
vector<int> g[N], fs[N];

int Find(int x) { return fa[x] ? fa[x] = Find(fa[x]) : x; }

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &r[i]);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int v = 1; v <= n; ++v) {
        for (int u : g[v]) {
            if (u < v) {
                int ru = Find(u);
                fs[v].push_back(ru);
                fa[ru] = v;
            }
        }
    }

    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int w : fs[u]) {
            dep[w] = dep[u] + 1;
            q.push(w);
        }
    }

    ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans = ans * ((r[i] + dep[i] + 1) % MOD) % MOD;
    }
    printf("%lld\n", ans);

    return 0;
}
0