結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-08-30 13:17:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 471 ms / 2,000 ms |
コード長 | 1,830 bytes |
コンパイル時間 | 2,852 ms |
コンパイル使用メモリ | 209,476 KB |
最終ジャッジ日時 | 2025-01-13 21:03:14 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 1000000007;struct unionfind{vector<int> p;vector<int> sz;unionfind(int N): p(vector<int>(N, -1)), sz(vector<int>(N, 1)){};int root(int x){if (p[x] == -1){return x;} else {p[x] = root(p[x]);return p[x];}}bool same(int x, int y){return root(x) == root(y);}void unite(int x, int y){x = root(x);y = root(y);if (x != y){p[x] = y;sz[y] += sz[x];}}int size(int x){return sz[root(x)];}};long long modpow(long long a, long long b){long long ans = 1;while (b > 0){if (b % 2 == 1){ans *= a;ans %= MOD;}a *= a;a %= MOD;b /= 2;}return ans;}int dfs(vector<vector<int>> &c, vector<int> &dp, int v = 0){for (int w : c[v]){dp[v] += dfs(c, dp, w);}return dp[v];}int main(){int N, M, X;cin >> N >> M >> X;vector<int> x(M), y(M), z(M);for (int i = 0; i < M; i++){cin >> x[i] >> y[i] >> z[i];x[i]--;y[i]--;}unionfind UF(N);vector<vector<pair<long long, int>>> E(N);for (int i = 0; i < M; i++){if (!UF.same(x[i], y[i])){UF.unite(x[i], y[i]);long long c = modpow(X, z[i]);E[x[i]].push_back(make_pair(c, y[i]));E[y[i]].push_back(make_pair(c, x[i]));}}vector<int> p(N, -1);vector<long long> d(N, 0);vector<vector<int>> c(N);queue<int> Q;Q.push(0);while (!Q.empty()){int v = Q.front();Q.pop();for (auto P : E[v]){int w = P.second;if (w != p[v]){p[w] = v;d[w] = P.first;c[v].push_back(w);Q.push(w);}}}vector<int> dp(N, 1);dfs(c, dp);long long ans = 0;for (int i = 1; i < N; i++){ans += d[i] * dp[i] % MOD * (N - dp[i]) % MOD;ans %= MOD;}cout << ans << endl;}