結果
| 問題 |
No.1843 Tree ANDistance
|
| ユーザー |
 ooaiu
|
| 提出日時 | 2025-07-24 23:03:42 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 126 ms / 2,000 ms |
| コード長 | 9,435 bytes |
| コンパイル時間 | 3,231 ms |
| コンパイル使用メモリ | 286,556 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-07-24 23:03:51 |
| 合計ジャッジ時間 | 8,784 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 38 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
template <class F> class y_combinator {
F f;
public:
y_combinator(F&& f) : f(std::forward<F>(f)) {}
template <class... Args> auto operator()(Args&&... args) const { return f(*this, std::forward<Args>(args)...); }
};
using ll = long long;
using ld = long double;
template <class T, class U = std::less<T>> using prique = std::priority_queue<T, std::vector<T>, U>;
template <class T> T floor(T a, T b) noexcept { return a / b - (a % b && (a ^ b) < 0); }
template <class T> T ceil(T a, T b) noexcept { return floor(a + b - 1, b); }
template <class T> bool chmin(T& x, const T& y) noexcept { return (x > y ? x = y, true : false); }
template <class T> bool chmax(T& x, const T& y) noexcept { return (x < y ? x = y, true : false); }
#define overload4(a, b, c, d, e, ...) e
#define rep1(a) for (long long _i = 0; _i < (a); _i++)
#define rep2(i, a) for (long long i = 0; i < (a); i++)
#define rep3(i, a, b) for (long long i = (a); i < (b); i++)
#define rep4(i, a, b, c) for (long long i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(i, a, b, c) for (long long i = (a); i > (b); i += (c))
#define all(x) std::begin(x), std::end(x)
#define rall(x) std::rbegin(x), std::rend(x)
#define pb push_back
#ifndef LOCAL
#define debug(...)
#endif
class UnionFind {
int n, c;
std::vector<int> d;
int find(int p) {
return (d[p] < 0 ? p : d[p] = find(d[p]));
}
public:
explicit UnionFind(int n = 0) : n(n), d(n, -1){};
int leader(int v) {
assert(0 <= v && v < n);
return find(v);
}
int merge(int a, int b) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
int la = leader(a), lb = leader(b);
if (la == lb) return la;
if (d[la] > d[lb]) std::swap(la, lb);
d[la] += d[lb];
d[lb] = la;
return la;
}
bool same(int a, int b) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
return leader(a) == leader(b);
}
int size(int v) {
assert(0 <= v && v < n);
return -d[leader(v)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> buf(n), sz(n);
for (int i = 0; i < n; i++) {
buf[i] = leader(i);
sz[buf[i]]++;
}
std::vector<std::vector<int>> res(n);
for (int i = 0; i < n; i++) res[i].reserve(sz[i]);
for (int i = 0; i < n; i++) res[buf[i]].push_back(i);
res.erase(
std::remove_if(res.begin(), res.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
res.end());
return res;
}
};
namespace internal {
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
constexpr long long pow_mod_constexpr(long long x, long long n, int m_) {
if (m_ == 1) return 0;
unsigned int m = static_cast<unsigned int>(m_);
unsigned long long r = 1, y = safe_mod(x, m);
while (n) {
if (n & 1) {
r = (r * y) % m;
}
y = (y * y) % m;
n >>= 1;
}
return r;
}
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long t = n - 1;
while (t % 2 == 0) t /= 2;
constexpr long long base[3] = {2, 7, 61};
for (long long a : base) {
long long d = t;
long long v = pow_mod_constexpr(a, t, n);
if (v == 1) continue;
while (d != n - 1 && v != n - 1) {
v = v * v % n;
d <<= 1;
}
if (v != n - 1) return false;
}
return true;
}
template <int n>
constexpr bool is_prime = is_prime_constexpr(n);
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
constexpr long long inv_mod(long long x, long long m) {
assert(1 <= m);
auto z = inv_gcd(x, m);
assert(z.first == 1);
return z.second;
}
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; i <= x / i; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) x /= i;
}
}
if (x > 1) divs[cnt++] = x;
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m>
constexpr int primitive_root = primitive_root_constexpr(m);
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
template <unsigned m>
class StaticModint {
unsigned value;
using mint = StaticModint;
static constexpr bool is_prime = internal::is_prime<m>;
static constexpr unsigned umod() { return m; }
public:
static constexpr unsigned mod() { return m; }
static mint raw(int v) {
mint x;
x.value = v;
return x;
}
StaticModint() : value(0) {}
template <class T, std::enable_if_t<std::is_integral_v<T>, int> = false>
StaticModint(T v) { value = static_cast<unsigned>(internal::safe_mod(v, m)); }
int val() const { return value; }
mint& operator++() {
value = (value + 1 == umod() ? 0 : value + 1);
return *this;
}
mint& operator--() {
value = (value == 0 ? umod() - 1 : value - 1);
return *this;
}
mint operator++(int) {
mint res = *this;
++*this;
return res;
}
mint operator--(int) {
mint res = *this;
--*this;
return res;
}
mint& operator+=(const mint& rhs) {
value += rhs.value;
if (value >= umod()) value -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
if (value < rhs.value) value += umod();
value -= rhs.value;
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = value;
z *= rhs.value;
value = static_cast<unsigned>(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
for (; n; n >>= 1, x *= x)
if (n & 1) r *= x;
return r;
}
mint inv() const { return (is_prime ? pow(m - 2) : internal::inv_mod(value, m)); }
friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
friend bool operator==(const mint& lhs, const mint& rhs) { return lhs.value == rhs.value; }
friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs.value != rhs.value; }
template <class Pr> void print(Pr& p) const { p << value; }
template <class Sc> void scan(Sc& s) { s >> value; }
};
using modint998 = StaticModint<998244353>;
using modint107 = StaticModint<1000000007>;
using mint = modint107;
void run_case() {
int N;
cin >> N;
vector<array<int, 3>> E;
rep(i, 1, N) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
E.pb({a, b, c});
}
mint ans = 0;
rep(it, 31) {
UnionFind uf(N);
for (const auto& [a, b, c] : E) {
if (c >> it & 1) {
uf.merge(a, b);
}
}
rep(root, N) {
ll t = uf.size(root);
ans += mint::raw(2).pow(it) * (t - 1);
}
}
ans /= 2;
cout << ans.val() << "\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::fixed(std::cout).precision(16);
int T = 1;
while (T--) run_case();
return 0;
}