#include using namespace std; using ll = long long; using str = string; #define re(n) for(int _=0;_=0; i--) #define per1(i,s,n) for(int i=int(n)-1; i>=s; i--) #define all(x) x.begin(), x.end() #define SORT(v) sort(all(v)) #define REV(v) reverse(all(v)) #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define elif else if #define len(x) ll(x.size()) #define _GLIBCXX_DEBUG template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } templatevoid vcin(vector &n){for(int i=0;i>n[i];} templatevoid vcout(vector &n){for(int i=0;i; using vvi = vector; using pii = pair; using vl = vector; using vvl = vector; using pll = pair; using vpi = vector; using vpl = vector; using vc = vector; using vs = vector; using quei = deque; using quel = deque; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") int main() { // 高速な入出力 ios_base::sync_with_stdio(false); cin.tie(NULL); // 問題で指定される法(剰余) const ll mod = 1e9 + 7; int n; cin >> n; // 隣接リストでグラフ(木)を表現します // g[u] には、頂点uに接続する頂点vと辺の重みcのペア {v, c} が格納されます vector>> g(n); for (int i = 0; i < n - 1; ++i) { int u, v, c; cin >> u >> v >> c; // 1-based indexから0-based indexに変換 u--; v--; g[u].push_back({v, c}); g[v].push_back({u, c}); } // DFS(深さ優先探索)で木の走査順序(後行順)を決定します // これにより、動的計画法で親を計算する際に、子の計算が完了していることを保証します vector order; order.reserve(n); vector st; st.push_back(0); // 頂点0から探索開始 vector seen(n, false); seen[0] = true; while (!st.empty()) { int u = st.back(); st.pop_back(); order.push_back(u); for (auto const& edge : g[u]) { int v = edge.first; if (seen[v]) { continue; } seen[v] = true; st.push_back(v); } } // DFSで得られる順序は先行順なので、逆順にして後行順にします reverse(order.begin(), order.end()); ll ans = 0; // 0から29までの各ビットについて計算を独立して行います for (int i = 0; i < 30; ++i) { // dp[u]: i番目のビットが立った辺のみで構成される、uのサブツリー内で始まりuで終わるパスの数 // -1で初期化し、未訪問の親と計算済の子を区別します vector dp(n, -1); ll p2 = 1LL << i; // 2^i を事前に計算 // 後行順で各頂点を処理 for (int u : order) { // tmp: uの各子vから計算されたパス数(ret)を格納するリスト vector tmp; tmp.reserve(g[u].size()); for (auto const& edge : g[u]) { int v = edge.first; int c = edge.second; // dp[v]が-1なら、vはuの親なのでスキップ if (dp[v] == -1) { continue; } ll ret = 0; // 辺(u,v)の重みのi番目のビットが1の場合 if ((c >> i) & 1) { // vのサブツリーからvへ至るパス(dp[v]個)をuまで延長したものと、 // vから始まる新しいパス{v,u}の1つを合わせて、uで終わるパスの数とする ret = dp[v] + 1; } // i番目のビットが0なら、パスは途切れるので ret = 0 tmp.push_back(ret); } ll S = 0; // tmpの合計 ll t = 0; // tmpの各要素の二乗和 for (ll ret_val : tmp) { // 1. uで終わるパスの貢献 // ret_val個の各パスは、最終的な答えに 2^i だけ貢献します ans = (ans + (ret_val % mod * (p2 % mod)) % mod) % mod; // 2. uを通過するパスの計算のための準備 // Pythonの任意精度整数と同様に、64ビット整数の最大値を超えない範囲で計算 S += ret_val; t += ret_val * ret_val; } // 2. uを通過するパスの貢献 // 異なる2つのサブツリーから来たパスをuで繋ぐ場合の数 (Σ ret_j * ret_k) は // (S^2 - t) / 2 で計算できます ll term_val = (S * S - t) / 2; // この貢献分も答えに加算 ans = (ans + (term_val % mod * (p2 % mod)) % mod) % mod; // uのDPテーブルを更新 dp[u] = S; } } cout << ans << endl; return 0; }