結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-08-30 17:32:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 400 ms / 2,000 ms |
コード長 | 2,686 bytes |
コンパイル時間 | 1,512 ms |
コンパイル使用メモリ | 111,708 KB |
実行使用メモリ | 42,904 KB |
最終ジャッジ日時 | 2024-11-15 13:52:47 |
合計ジャッジ時間 | 16,357 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include<stdio.h>#include<iostream>#include<algorithm>#include<vector>#include<string>#include<utility>#include<map>#include<set>#include<queue>#include<stack>#include<functional>#include<math.h>#include<random>#include <bitset>using namespace std;#define N (1000000000+7)//#define N 998244353#define INF 1e16typedef long long ll;typedef pair<int,int> P;typedef pair<int,P> Q;const int inf = (int)1e9;ll gcd(ll a, ll b) {if (b > a) {ll tmp = b;b = a;a = tmp;}if (a%b == 0)return b;else return gcd(b, a%b);}class UnionFind {public:vector<int>par, rank, node;UnionFind(int n) :par(n), rank(n, 0),node(n,1) {for (int i = 0;i < n;i++)par[i] = i;}void init(int n) {for (int i = 0;i < n;i++) {par[i] = i;rank[i] = 0;node[i] = 1;}}int find(int x) {return par[x] == x ? x : par[x] = find(par[x]);}bool same(int x, int y) {return find(x) == find(y);}void unite_tree(int x, int y) {x = find(x);y = find(y);if (x == y)return;if (rank[x] < rank[y]) {par[x] = y;}else {par[y] = x;if (rank[x] == rank[y])rank[x]++;}}int root_size(int x){return rank[find(x)];}int size(int x) {return node[find(x)];}void unite_node(int x, int y) {x = find(x);y = find(y);if (x == y)return;if (size(x) < size(y))swap(x, y);node[x] += node[y];par[y] = par[x];}};ll x;struct edge{int from;int to;ll cost;};struct E{int to;ll cost;};vector<E>g[200010];ll inv(ll x,ll power) {ll res = 1;ll k = power;ll y = x%N;while (k) {if (k & 1)res = (res*y) % N;y = (y%N*y%N) % N;k /= 2;}return res;}ll dfs(int v, int p, ll n, ll &ans) {ll ret = 0;for (auto e: g[v]) {int to = e.to;ll cost = inv(x,e.cost);if (to == p) continue;ll a = dfs(to, v, n, ans);ll t = (((cost*a)%N)*(n-a))%N;ans = (ans+t)%N;ret = (ret+a)%N;}return (ret + 1)%N;}int main(void){ll n,m;cin>>n>>m>>x;UnionFind uf = UnionFind(n);vector<edge>e;for(int i=0;i<m;i++){int a,b;ll z;cin>>a>>b>>z;a--;b--;e.push_back({a,b,z});}auto f = [&](edge &a,edge &b){return a.cost<b.cost;};sort(e.begin(),e.end(),f);for(int i=0;i<m;i++){int u = e[i].from;int v = e[i].to;ll c = e[i].cost;if(!uf.same(u,v)){uf.unite_node(u,v);g[u].push_back({v,c});g[v].push_back({u,c});}}ll ans = 0;dfs(0,-1,n,ans);cout<<ans<<endl;return 0;}