結果
問題 | No.1843 Tree ANDistance |
ユーザー |
|
提出日時 | 2022-02-19 19:53:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 652 ms / 2,000 ms |
コード長 | 659 bytes |
コンパイル時間 | 5,355 ms |
コンパイル使用メモリ | 313,624 KB |
実行使用メモリ | 9,940 KB |
最終ジャッジ日時 | 2024-06-29 10:39:02 |
合計ジャッジ時間 | 18,468 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endif#define rep(i, n) for (int i = 0; i < (n); ++i)using std::cin;using std::cout;using std::vector;using std::array;using mint = modint1000000007;int main() {int n;cin >> n;vector<array<int, 3>> es(n-1);for (auto& [a, b, c] : es) {cin >> a >> b >> c;--a; --b;}mint ans;rep(i, 30) {dsu t(n);for (auto& [a, b, c] : es) {if (c>>i&1) {t.merge(a, b);}}for (auto g : t.groups()) {mint x = g.size();x = x * (x-1) / 2;ans += x * (1<<i);}}cout << ans.val() << '\n';return 0;}