結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-08-30 14:01:52 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,424 bytes |
コンパイル時間 | 3,745 ms |
コンパイル使用メモリ | 78,372 KB |
実行使用メモリ | 114,320 KB |
最終ジャッジ日時 | 2024-12-27 15:27:01 |
合計ジャッジ時間 | 63,105 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 TLE * 1 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main {static List<List<Hen>> list;public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] sa = br.readLine().split(" ");int n = Integer.parseInt(sa[0]);int m = Integer.parseInt(sa[1]);int x = Integer.parseInt(sa[2]);list = new ArrayList<>(n);for (int i = 0; i < n; i++) {list.add(new ArrayList<>());}UnionFind uf = new UnionFind(n);List<Hen> hens = new ArrayList<>();for (int i = 0; i < m; i++) {sa = br.readLine().split(" ");Hen h = new Hen();h.x = Integer.parseInt(sa[0]) - 1;h.y = Integer.parseInt(sa[1]) - 1;h.z = Integer.parseInt(sa[2]);if (!uf.same(h.x, h.y)) {uf.union(h.x, h.y);list.get(h.x).add(h);list.get(h.y).add(h);hens.add(h);}}br.close();dfs(0, -1);int mod = 1000000007;long ans = 0;for (Hen h : hens) {long cnt = (long) h.c * (n - h.c) % mod;ans += power(x, h.z, mod) * cnt;ans %= mod;}System.out.println(ans);}static int dfs(int cur, int p) {int ret = 1;List<Hen> nexts = list.get(cur);for (Hen h : nexts) {int next = h.x;if (next == cur) {next = h.y;}if (next == p) {continue;}h.c = dfs(next, cur);ret += h.c;}return ret;}static class Hen {int x, y, z, c;}static long power(long x, long n, int m) {if (n == 0) {return 1;}long val = power(x, n / 2, m);val = val * val % m;if (n % 2 == 1) {val = val * x % m;}return val;}static class UnionFind {int[] parent, size;int num = 0; // 連結成分の数UnionFind(int n) {parent = new int[n];size = new int[n];num = n;for (int i = 0; i < n; i++) {parent[i] = i;size[i] = 1;}}void union(int x, int y) {int px = find(x);int py = find(y);if (px != py) {parent[px] = py;size[py] += size[px];num--;}}int find(int x) {if (parent[x] == x) {return x;}parent[x] = find(parent[x]);return parent[x];}/*** xとyが同一連結成分か*/boolean same(int x, int y) {return find(x) == find(y);}/*** xを含む連結成分のサイズ*/int size(int x) {return size[find(x)];}}}