結果
問題 | No.1207 グラフX |
ユーザー |
|
提出日時 | 2020-08-30 13:53:44 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 787 ms / 2,000 ms |
コード長 | 2,881 bytes |
コンパイル時間 | 1,093 ms |
コンパイル使用メモリ | 141,636 KB |
実行使用メモリ | 57,324 KB |
最終ジャッジ日時 | 2024-06-22 08:44:27 |
合計ジャッジ時間 | 28,560 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm;import std.typecons, std.range, std.random, std.math, std.container;import std.numeric, std.bigint, core.bitop, core.stdc.stdlib, std.datetime;immutable long MOD = 10^^9 + 7;void main() {auto s = readln.split.map!(to!int);auto N = s[0];auto M = s[1];auto X = s[2].to!long;long score(long c) {return powmod(X, c, MOD);}Tuple!(int, int, long)[] E;foreach (_; 0..M) {s = readln.split.map!(to!int);auto a = s[0] - 1;auto b = s[1] - 1;auto c = s[2].to!long;E ~= tuple(a, b, c);}E.sort!"a[2] < b[2]";auto uf = new UnionFind(N);auto G = new Tuple!(int, long)[][](N);foreach (e; E) {auto a = e[0];auto b = e[1];auto c = e[2];if (uf.find(a) == uf.find(b)) continue;uf.unite(a, b);G[a] ~= tuple(b, c);G[b] ~= tuple(a, c);}auto sub = new int[](N);void dfs1(int n, int p) {sub[n] = 1;foreach (e; G[n]) {auto m = e[0];if (m != p) {dfs1(m, n);sub[n] += sub[m];}}}dfs1(0, -1);auto dp = new long[](N);void dfs2(int n, int p) {foreach (e; G[n]) {auto m = e[0];auto c = e[1];if (m != p) {dfs2(m, n);dp[n] += dp[m] + sub[m] * score(c) % MOD;dp[n] %= MOD;}}}dfs2(0, -1);auto ans = new long[](N);void dfs3(int n, int p, long cp) {if (p == -1) {ans[n] = dp[n];} else {ans[n] = ans[p] - sub[n] * score(cp) % MOD + (N - sub[n]) * score(cp) % MOD;ans[n] = (ans[n] % MOD + MOD) % MOD;}foreach (e; G[n]) {auto m = e[0];auto c = e[1];if (m != p) dfs3(m, n, c);}}dfs3(0, -1, 0);long ansans = 0;foreach (a; ans) (ansans += a) %= MOD;ansans = ansans * powmod(2, MOD-2, MOD) % MOD;ansans.writeln;}class UnionFind {import std.algorithm : swap;int n;int[] table;this(int n) {this.n = n;table = new int[](n);table[] = -1;}int find(int x) {return table[x] < 0 ? x : (table[x] = find(table[x]));}void unite(int x, int y) {x = find(x);y = find(y);if (x == y) return;if (table[x] > table[y]) swap(x, y);table[x] += table[y];table[y] = x;}bool same(int x, int y) {return find(x) == find(y);}}long powmod(long a, long x, long m) {long ret = 1;while (x) {if (x % 2) ret = ret * a % m;a = a * a % m;x /= 2;}return ret;}