結果

問題 No.1207 グラフX
ユーザー rabimea
提出日時 2025-09-27 07:51:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 1,341 bytes
コンパイル時間 3,134 ms
コンパイル使用メモリ 285,640 KB
実行使用メモリ 34,532 KB
最終ジャッジ日時 2025-09-27 07:51:51
合計ジャッジ時間 12,716 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>

using std::cin, std::cout, std::cerr;
using ll = long long;

const ll P = 1e9 + 7;
ll Pow(ll a, ll b) {
    ll r = 1;
    for(; b; b /= 2) {
        if(b & 1)
            r = r * a % P;
        a = a * a % P;
    }
    return r;
}

int main() {
    std::ios::sync_with_stdio(false);
    int n, m, b; cin >> n >> m >> b;
    std::vector<int> p(n + 1);
    std::iota(p.begin(), p.end(), 0);
    std::function<int(int)> root = [&](int x) {
        if(p[x] == x) return x;
        return p[x] = root(p[x]);
    };

    std::vector<std::vector<std::pair<int, int>>> e(n + 1);
    for(int i = 0; i < m; i ++) {
        int x, y, z; cin >> x >> y >> z;
        int rx = root(x);
        int ry = root(y);
        if(rx != ry) {
            e[x].push_back({y, z});
            e[y].push_back({x, z});
            p[ry] = rx;
        }
    }

    ll ans = 0;
    std::vector<int> sz(n + 1);
    std::function<void(int, int)> dfs = [&](int x, int p) {
        sz[x] = 1;
        for(auto [i, z] : e[x]) if(i != p) {
            dfs(i, x);
            sz[x] += sz[i];
            ans += ll(sz[i]) * (n - sz[i]) % P * Pow(b, z);
            ans %= P;
        }
    };
    dfs(1, 0);
    cout << ans % P << '\n';
}
0