結果

問題 No.1843 Tree ANDistance
ユーザー Yotugi
提出日時 2025-06-10 23:02:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 415 ms / 2,000 ms
コード長 5,534 bytes
コンパイル時間 4,190 ms
コンパイル使用メモリ 296,684 KB
実行使用メモリ 12,264 KB
最終ジャッジ日時 2025-06-10 23:03:02
合計ジャッジ時間 11,756 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using str = string;
#define re(n) for(int _=0;_<int(n);_++)
#define rep(i,n) for(int i=0; i<int(n); i++)
#define rep1(i,s,n) for(int i=int(s); i<int(n); i++)
#define rep2(i,s,n,a) for (ll i = a; i < ll(n); i += (a))
#define per(i,n) for(int i=int(n)-1; i>=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<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
using vi = vector<int>; 
using vvi = vector<vi>;
using pii = pair<int, int>;
using vl = vector<ll>; 
using vvl = vector<vl>;
using pll = pair<ll, ll>;
using vpi = vector<pii>;
using vpl = vector<pll>;
using vc = vector<char>; 
using vs = vector<str>;
using quei = deque<int>;
using quel = deque<ll>;


#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<vector<pair<int, int>>> 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<int> order;
    order.reserve(n);
    vector<int> st;
    st.push_back(0); // 頂点0から探索開始
    vector<bool> 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<ll> dp(n, -1);
        ll p2 = 1LL << i; // 2^i を事前に計算

        // 後行順で各頂点を処理
        for (int u : order) {
            // tmp: uの各子vから計算されたパス数（ret）を格納するリスト
            vector<ll> 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;
}
0