結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-10-08 10:12:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 222 ms / 2,000 ms |
コード長 | 3,802 bytes |
コンパイル時間 | 1,946 ms |
コンパイル使用メモリ | 177,076 KB |
実行使用メモリ | 27,448 KB |
最終ジャッジ日時 | 2024-07-20 05:48:52 |
合計ジャッジ時間 | 10,613 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (int)(n); i ++) #define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i) using namespace std; using ll = long long; using PL = pair<ll,ll>; using P = pair<int,int>; constexpr int INF = 1000000000; constexpr long long HINF = 1000000000000000; constexpr long long MOD = 1000000007;// = 998244353; constexpr double EPS = 1e-4; constexpr double PI = 3.14159265358979; struct UnionFind { int N; vector<int> parents; UnionFind(int _N) : N(_N){ parents.assign(N,-1); } int find(int x) { //xの親を返す if (parents[x] < 0) return x; return parents[x] = find(parents[x]); } void unite(int x, int y) { //xとyの含むグループを併合 int px = find(x); int py = find(y); if (parents[px] > parents[py]) swap(px,py); if (px != py) { parents[px] += parents[py]; parents[py] = px; } } bool same(int x, int y) { //x,yが同じグループにいるか判定 return find(x) == find(y); } int size(int x) { //xと同じグループのメンバーの個数 return -parents[find(x)]; } vector<int> root() {//ufの根を列挙 vector<int> res; for (int i = 0; i < N; i ++) { if (parents[i] < 0) res.push_back(i); } return res; } int group_count() { //ufのグループの数を数える int cnt = 0; for (int i = 0; i < N; i ++) { if (parents[i] < 0) cnt ++; } return cnt; } }; template<int Modulus> struct ModInt { long long x; ModInt(long long x = 0) :x((x%Modulus + Modulus)%Modulus) {} constexpr ModInt &operator+=(const ModInt a) {if ((x += a.x) >= Modulus) x -= Modulus; return *this;} constexpr ModInt &operator-=(const ModInt a) {if ((x += Modulus - a.x) >= Modulus) x -= Modulus; return *this;} constexpr ModInt &operator*=(const ModInt a) {(x *= a.x) %= Modulus; return *this;} constexpr ModInt &operator/=(const ModInt a) {return *this *= a.inverse();} constexpr ModInt operator+(const ModInt a) const {return ModInt(*this) += a.x;} constexpr ModInt operator-(const ModInt a) const {return ModInt(*this) -= a.x;} constexpr ModInt operator*(const ModInt a) const {return ModInt(*this) *= a.x;} constexpr ModInt operator/(const ModInt a) const {return ModInt(*this) /= a.x;} friend constexpr ostream& operator<<(ostream& os,const ModInt<Modulus>& a) {return os << a.x;} friend constexpr istream& operator>>(istream& is,ModInt<Modulus>& a) {return is >> a.x;} ModInt inverse() const {// x ^ (-1) long long a = x,b = Modulus,p = 1,q = 0; while (b) {long long d = a/b; a -= d*b; swap(a,b); p -= d*q; swap(p,q);} return ModInt(p); } ModInt pow(long long N) {// x ^ N ModInt a = 1; while (N) { if (N&1) a *= *this; *this *= *this; N >>= 1; } return a; } }; using mint = ModInt<1000000007>; mint ans = 0; int N; ll X; vector<vector<P>> G; int dfs(int v,int pa = -1) { int cnt = 1; for (const P &p:G[v]) { if (p.first == pa) continue; int c = dfs(p.first,v); ans += mint(N - c) * mint(c) * mint(X).pow(p.second); cnt += c; } return cnt; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int M; cin >> N >> M >> X; UnionFind uf(N); G.resize(N); rep(i,M) { int a,b,c; cin >> a >> b >> c; --a; --b; if (uf.same(a,b)) continue; uf.unite(a,b); G[a].emplace_back(b,c); G[b].emplace_back(a,c); } dfs(0); cout << ans << '\n'; return 0; }