結果
| 問題 |
No.1769 Don't Stop the Game
|
| コンテスト | |
| ユーザー |
 zjsdut
|
| 提出日時 | 2025-02-21 18:05:42 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 711 ms / 3,000 ms |
| コード長 | 29,390 bytes |
| コンパイル時間 | 1,454 ms |
| コンパイル使用メモリ | 134,172 KB |
| 実行使用メモリ | 58,132 KB |
| 最終ジャッジ日時 | 2025-02-21 18:05:54 |
| 合計ジャッジ時間 | 11,429 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
ソースコード
/**
* code generated by JHelperX
* More info: https://github.com/GoBigorGoHome/JHelperX
* @author zjs
*/
#if not defined LOCAL and not defined NDEBUG
#define NDEBUG
#endif
#if not defined LOCAL
#define debug(...)
#endif
extern const bool show_all_failed_tests = false;
extern const bool compare_real_numbers = false;
// #define INTERACTIVE_MODE //对于交互题，取消此行注释。
//
// Created by zjsdu on 5/28/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#include <string>
#include <cassert>
#include <queue>
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
#include <iostream>
#include <iomanip>
#include <vector>
#include <tuple>
//
// Created by zjsdu on 10/22/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
#define JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
#include <type_traits>
#if __cplusplus >= 201703L
template<typename T> T type();// no definition
template<typename Container> auto value_type_of_() {
if constexpr (std::is_array_v<Container>)
return type<std::remove_extent_t<Container>>();
else
return type<typename Container::value_type>();
}
template<typename Container>
using value_type_of =
decltype(value_type_of_<std::remove_reference_t<Container>>());
#else
template <typename Container>
struct value_type_of_impl // default, non-array
{
using type = typename Container::value_type;
};
template <typename T, std::size_t N>
struct value_type_of_impl<T[N]> // arrays
{
using type = T;
};
template <typename Container>
using value_type_of = typename value_type_of_impl<Container>::type;
#endif
// Source: https://foonathan.net/2020/10/iife-metaprogramming/
#if __cplusplus >= 201703L
namespace is_iterable_impl {
using std::begin;
using std::end;
template<typename T>
using check_specs = std::void_t<
std::enable_if_t<
std::is_same<decltype(begin(std::declval<T &>())),// has begin()
decltype(end(std::declval<T &>())) // has end()
>::value>,// ... begin() and end() are the same type ...
decltype(*begin(std::declval<T &>()))>;// ... which can be dereferenced
template<typename, typename = void> struct is_iterable : std::false_type {};
// specialization
template<class T> struct is_iterable<T, check_specs<T>> : std::true_type {};
}// namespace is_iterable_impl
template<class T> using is_iterable = is_iterable_impl::is_iterable<T>;
template<typename T> constexpr bool is_iterable_v = is_iterable<T>::value;
// Source: https://stackoverflow.com/a/53429396/6793559
template<typename T>
using is_string =
std::disjunction<std::is_same<char *, typename std::decay_t<T>>,
std::is_same<const char *, typename std::decay_t<T>>,
std::is_same<std::string, typename std::decay_t<T>>>;
template<typename T> constexpr bool is_string_v = is_string<T>::value;
// Source: https://stackoverflow.com/a/57812868/6793559
template<template<typename...> typename Target, typename Aux, typename... Ts>
struct is_specialized_for_impl : std::false_type {};
template<template<typename...> typename Target, typename... Args>
struct is_specialized_for_impl<Target, decltype(sizeof(Target<Args...>)),
Args...> : std::true_type {};
template<template<typename...> typename Target, typename... Args>
using is_specialized_for =
is_specialized_for_impl<Target, std::size_t, Args...>;
template<template<typename...> typename Target, typename... Args>
constexpr bool is_specialized_for_v =
is_specialized_for<Target, Args...>::value;
template<typename T>
using is_tuple_like = is_specialized_for<std::tuple_size, T>;
template<typename T> constexpr bool is_tuple_like_v = is_tuple_like<T>::value;
template<typename T, typename = void> struct remove_all_extents_ {
typedef std::remove_reference_t<T> type;
};
template<typename T>
struct remove_all_extents_<T, std::void_t<decltype(std::declval<T>()[0])>> {
typedef
typename remove_all_extents_<decltype(std::declval<T>()[0])>::type type;
};
template<typename T, typename = void>
struct rank_ : public std::integral_constant<std::size_t, 0> {};
template<typename T>
struct rank_<T, std::void_t<decltype(std::declval<T>()[0])>>
: public std::integral_constant<
std::size_t, rank_<decltype(std::declval<T>()[0])>::value + 1> {};
#endif
#endif// JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
struct fast_ios {
fast_ios() {
#ifndef INTERACTIVE_MODE
std::cin.tie(nullptr);
#endif
std::ios::sync_with_stdio(false);
std::cout.precision(15);
std::cout << std::fixed;
};
} const fast_ios_;
namespace io {
template<typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p);
template<typename... Ts>
std::istream &operator>>(std::istream &in, std::tuple<Ts...> &t);
template<typename... Ts>
std::ostream &operator<<(std::ostream &, const std::tuple<Ts...> &);
template<typename T, typename U>
std::istream &operator>>(std::istream &in, std::pair<T, U> &p) {
in >> p.first >> p.second;
return in;
}
template<typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &vec) {
for (auto &x : vec)
stream >> x;
return stream;
}
#if __cplusplus >= 201703L // fold expressions require C++17
template<typename... Ts>
std::istream &operator>>(std::istream &in, std::tuple<Ts...> &t) {
std::apply([&in](auto &...args) { ((in >> args), ...); }, t);
return in;
}
template<class... Args>
void scan(Args &...args) {
((std::cin >> args), ...);
}
template<typename Container,
typename = std::enable_if_t<std::conjunction_v<
is_iterable<Container>, std::negation<is_string<Container>>>>>
std::ostream &operator<<(std::ostream &out, const Container &container) {
using std::begin;
using value_type =
std::remove_reference_t<decltype(*begin(std::declval<Container &>()))>;
constexpr char delimiter =
is_iterable_v<value_type> or is_tuple_like_v<value_type> ? '\n' : ' ';
bool first = true;
for (auto &element : container) {
if (first)
first = false;
else
out << delimiter;
out << element;
}
return out;
}
// Source: https://en.cppreference.com/w/cpp/utility/apply
template<typename... Ts>
std::ostream &operator<<(std::ostream &out, const std::tuple<Ts...> &theTuple) {
std::apply(
[&out](Ts const &...tupleArgs) {
std::size_t n{0};
((out << tupleArgs << (++n != sizeof...(Ts) ? " " : "")), ...);
},
theTuple);
return out;
}
#endif
template<typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p) {
out << p.first << ' ' << p.second;
return out;
}
template<typename T>
std::ostream &operator<<(std::ostream &out,
const std::vector<std::vector<T>> &t) {
bool is_first = true;
for (const auto &row : t) {
if (is_first)
is_first = false;
else
out << '\n';
out << row;
}
return out;
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 n) {
using u64 = unsigned long long;
static const u64 B = 1e19;
if (n < B)
os << (u64) n;
else
os << n / B << std::setfill('0') << std::setw(19) << n % B;
return os;
}
std::ostream &operator<<(std::ostream &os, __int128 n) {
if (n < 0) {
os << '-' << (unsigned __int128) -n;
} else {
os << (unsigned __int128) n;
}
return os;
}
#if __cplusplus >= 201703L
template<typename... Args>
void pt(Args &&...args) {
((std::cout << args << ' '), ...);
}
template<typename First, typename... Args>
void pl(const First &first, const Args &...args) {
std::cout << first;
((std::cout << ' ' << args), ...);
std::cout << '\n';
}
template<typename... Args>
void pn(const Args &...args) {
((std::cout << args << '\n'), ...);
}
#endif
}// namespace io
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
//
// Created by zjsdu on 10/26/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
template<typename T, unsigned Dimension> struct ndvec {
using type = std::vector<typename ndvec<T, Dimension - 1>::type>;
};
template<typename T> struct ndvec<T, 0> { using type = T; };
// arbitrary-dimensional array that allows non-constexpr extents.
// Usage: ndarray<dimension, value_type> arr(extents..., init_value);
// An initial value for all array items can be specified if all extensions are
// specified.
// Examples:
// ndarray<2, int> a(2, 3, -1);
// ndarray<3, int> b(2, 3, 4);
// ndarray<3, int> c(2, 3);
template<unsigned dimension, typename T>
class ndarray : public ndvec<T, dimension>::type {
using base_type = typename ndvec<T, dimension>::type;
using value_type = typename base_type::value_type;
using base_type::base_type;
public:
template<typename... Args>
ndarray(unsigned d, Args... args)
: std::vector<value_type>(d, ndarray<dimension - 1, T>(args...)) {}
};
template<typename T> class ndarray<1, T> : public std::vector<T> {
using std::vector<T>::vector;
};
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
//
// Created by zjsdu on 2/9/2021.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
#define CALL_WITH_EXPANDED_ARGS(function, ...) function(__VA_ARGS__)
#define JOIN_IMPL(arg1, arg2) arg1##arg2
#define JOIN(arg1, arg2) JOIN_IMPL(arg1, arg2)
#define EXPAND_1(...) __VA_ARGS__
#define EXPAND_4(...) EXPAND_1(EXPAND_1(EXPAND_1(__VA_ARGS__)))
#define EXPAND_13(...) EXPAND_4(EXPAND_4(EXPAND_4(__VA_ARGS__)))
#define PAUSE
#define COMMA() ,
#define TERMINATE(...)
#define SELECT_SECOND_ARG(arg1, arg2, ...) arg2
#define CONDITIONAL(peek, arg1, arg2) \
CALL_WITH_EXPANDED_ARGS(SELECT_SECOND_ARG, COMMA peek arg1, arg2)
#define TERMINATE_OR(peek, arg) CONDITIONAL(peek, TERMINATE, arg)
#define FOR_EACH_2_IMPL0(function, arg1, arg2, peek, ...) \
function(arg1, arg2) TERMINATE_OR(peek, FOR_EACH_2_IMPL1) \
PAUSE(function, peek, __VA_ARGS__)
#define FOR_EACH_2_IMPL1(function, arg1, arg2, peek, ...) \
function(arg1, arg2) TERMINATE_OR(peek, FOR_EACH_2_IMPL0) \
PAUSE(function, peek, __VA_ARGS__)
#define FOR_EACH_2(function, ...) \
EXPAND_13(FOR_EACH_2_IMPL0(function, __VA_ARGS__, ()))
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using vl = std::vector<ll>;
using vb = std::vector<bool>;
using vi = std::vector<int>;
using vs = std::vector<std::string>;
using pii = std::pair<int, int>;
using pli = std::pair<ll, int>;
using pil = std::pair<int, ll>;
using pll = std::pair<ll, ll>;
using vii = std::vector<pii>;
template<typename T>
using pq = std::priority_queue<T>;
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<typename... Ts> using vt = std::vector<std::tuple<Ts...>>;
template<typename T> using vv = ndarray<2, T>;
template<typename T> struct range_tuple {
const T &ref = beg;
T beg;
const T end;
range_tuple(T b, T e) : beg(b), end(e) {}
};
#define rng4(i, a, b, c) \
for (auto &&[i, JOIN(iter_, __LINE__), JOIN(end_, __LINE__)] = \
range_tuple<std::common_type_t<decltype(a), decltype(b)>>(a, b); \
i < JOIN(end_, __LINE__); JOIN(iter_, __LINE__) += c)
#define rng3(i, a, b) rng4(i, a, b, 1)
#define rng2(i, n) rng3(i, 0, n)
#define GET4(_1, _2, _3, _4, NAME, ...) NAME
#define rng(...) GET4(__VA_ARGS__, rng4, rng3, rng2)(__VA_ARGS__)
#define up4(i, a, b, c) rng (i, a, b + 1, c)
#define up3(i, a, b) up4(i, a, b, 1)
#define up(...) GET4(__VA_ARGS__, up4, up3, NO_IMPL)(__VA_ARGS__)
#define down4(i, b, a, c) \
for (auto &&[i, JOIN(iter_, __LINE__), JOIN(end_, __LINE__)] = \
range_tuple<std::common_type_t<decltype(a), decltype(b)>>(b, a); \
i >= JOIN(end_, __LINE__); JOIN(iter_, __LINE__) -= c)
#define down3(i, b, a) down4(i, b, a, 1)
#define down(...) GET4(__VA_ARGS__, down4, down3, NO_IMPL)(__VA_ARGS__)
#define rep(n) \
for (auto JOIN(_iter_, __LINE__) = n; JOIN(_iter_, __LINE__) > 0; \
--JOIN(_iter_, __LINE__))
#define FOR_LAST_OPERATION_IMPL(arg1, arg2) arg1] : arg2
#define FOR_NORMAL_OPERATION_IMPL(arg1, arg2) arg1,
#define FOR_IMPL0(arg1, arg2, peek, ...) \
CONDITIONAL(peek, FOR_LAST_OPERATION_IMPL, FOR_NORMAL_OPERATION_IMPL) \
(arg1, arg2) TERMINATE_OR(peek, FOR_IMPL1) PAUSE(arg2, peek, __VA_ARGS__)
#define FOR_IMPL1(arg1, arg2, peek, ...) \
CONDITIONAL(peek, FOR_LAST_OPERATION_IMPL, FOR_NORMAL_OPERATION_IMPL) \
(arg1, arg2) TERMINATE_OR(peek, FOR_IMPL0) PAUSE(arg2, peek, __VA_ARGS__)
#define FOR_IMPL3(arg1, arg2, peek, ...) \
CONDITIONAL(peek, for (auto && arg1 : arg2), \
for (auto && [EXPAND_13(FOR_IMPL0(arg1, arg2, peek, __VA_ARGS__))))
#define FOR(...) FOR_IMPL3(__VA_ARGS__, ())
#define ALL(x) std::begin(x), std::end(x)
// hat off to 300iq
#define RALL(x) std::rbegin(x), std::rend(x)
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define ep emplace
#define SZ(x) (int) (x).size()
#define rp(...) return pl(__VA_ARGS__)
#define rpn(...) return pn(__VA_ARGS__)
#define adv(i, n) \
for (auto JOIN(_n_, __LINE__) = n; i < JOIN(_n_, __LINE__); ++i)
#define radv(i, n) \
for (auto JOIN(_n_, __LINE__) = n; i > JOIN(_n_, __LINE__); --i)
#define INT(...) \
int __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define LL(...) \
long long __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define STR(...) \
std::string __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define NL \
[] { \
std::cout << '\n'; \
}()
#define RI \
([] { \
int x; \
std::cin >> x; \
return x; \
})()
#define READ_VI(NAME, LEN) \
std::vector<int> NAME(LEN); \
io::scan(NAME);
#define VI(...) FOR_EACH_2(READ_VI, __VA_ARGS__)
#define READ_VII(NAME, LEN) \
std::vector<std::pair<int, int>> NAME(LEN); \
io::scan(NAME);
#define VII(...) FOR_EACH_2(READ_VII, __VA_ARGS__)
#define READ_VL(NAME, LEN) \
std::vector<long long> NAME(LEN); \
io::scan(NAME);
#define VL(...) FOR_EACH_2(READ_VL, __VA_ARGS__)
#define READ_VS(NAME, LEN) \
std::vector<std::string> NAME(LEN); \
io::scan(NAME);
#define VS(...) FOR_EACH_2(READ_VS, __VA_ARGS__)
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#ifndef CP_UTILS
#define CP_UTILS
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <map>
#include <unordered_map>
#include <numeric>
#include <set>
#include <random>
#include <chrono>
inline void Yn(bool p) {
std::cout << (p ? "Yes\n" : "No\n");
}
inline void YN(bool p) {
std::cout << (p ? "YES\n" : "NO\n");
}
inline void yn(bool p) {
std::cout << (p ? "yes\n" : "no\n");
}
template<typename Container> Container inc(Container &&c) {
for (auto &e : c)
++e;
return std::forward<Container>(c);
}
template<typename Container> Container dec(Container &&c) {
for (auto &e : c)
--e;
return std::forward<Container>(c);
}
template<typename A, typename B>
bool chkmin(A& a, const B& b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename A, typename B>
bool chkmax(A& a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#if __cplusplus >= 201703L
template<typename A, typename B, typename... C>
bool chkmin(A& a, const B& b, const C&... c) {
if (B res = std::min<B>({b, c...}); res < a) {
a = res;
return true;
}
return false;
}
template<typename A, typename B, typename... C>
bool chkmax(A& a, const B& b, const C&... c) {
if (B res = std::max<B>({b, c...}); res > a) {
a = res;
return true;
}
return false;
}
#endif
template<typename T, typename U>
void append(T &container1, const U &container2) {
container1.insert(container1.end(), container2.begin(), container2.end());
}
template<typename T> int argmin(const std::vector<T> &a) {
return (int) (std::min_element(a.begin(), a.end()) - a.begin());
}
template<typename T> int argmax(const std::vector<T> &a) {
return (int) (std::max_element(a.begin(), a.end()) - a.begin());
}
template<typename Container> Container reverse(Container &&c) {
std::reverse(std::begin(c), std::end(c));
return std::forward<Container>(c);
}
template<typename Sequence> Sequence rev_copy(Sequence a) {
std::reverse(std::begin(a), std::end(a));
return a;
}
template<typename Sequence> Sequence uniq(Sequence &&s) {
std::sort(std::begin(s), std::end(s));
s.erase(std::unique(std::begin(s), std::end(s)), std::end(s));
return std::forward<Sequence>(s);
}
template<typename Container> auto max(const Container &c) {
assert(c.size() > 0);
return *std::max_element(std::begin(c), std::end(c));
}
template<typename Container> auto min(const Container &c) {
assert(c.size() > 0);
return *std::min_element(std::begin(c), std::end(c));
}
template<typename Array, typename Value> auto lb(Array &a, Value v) {
return std::lower_bound(std::begin(a), std::end(a), v);
}
template<typename Array, typename Value> auto ub(Array &a, Value v) {
return std::upper_bound(std::begin(a), std::end(a), v);
}
template<typename Array, typename Value, typename Compare>
auto lb(const Array &a, Value v, Compare compare) {
return std::lower_bound(std::begin(a), std::end(a), v, compare);
}
template<typename Array, typename Value, typename Compare>
auto ub(const Array &a, Value v, Compare compare) {
return std::upper_bound(std::begin(a), std::end(a), v, compare);
}
template<typename Array, typename Value> int lbi(const Array &a, Value v) {
return int(lb(a, v) - std::begin(a));
}
template<typename Iter, typename Value> int lbi(Iter beg, int count, Value v) {
assert(count > 0);
return int(std::lower_bound(beg, beg + count, v) - beg);
}
template<typename Iter, typename Value> int ubi(Iter beg, int count, Value v) {
assert(count > 0);
return int(std::upper_bound(beg, beg + count, v) - beg);
}
template<typename Array, typename Value> int ubi(const Array &a, Value v) {
return int(ub(a, v) - std::begin(a));
}
template<typename Container>
Container iota(Container &&c, value_type_of<Container> v) {
std::iota(std::begin(c), std::end(c), v);
return std::forward<Container>(c);
}
template<typename T, typename Comp>
std::vector<int> argsort(const std::vector<T> &array, Comp comp) {
std::vector<int> res(array.size());
std::iota(res.begin(), res.end(), 0);
std::stable_sort(res.begin(), res.end(), [&array, comp](int i, int j) {
return comp(array[i], array[j]);
});
return res;
}
template<typename T> std::vector<int> argsort(const std::vector<T>& array) {
std::vector<int> res(array.size());
std::iota(res.begin(), res.end(), 0);
std::stable_sort(res.begin(), res.end(),
[&array](int i, int j) { return array[i] < array[j]; });
return res;
}
#if __cplusplus >= 201703L
template<typename Container, typename Compare = void *>
Container sort(Container &&c, Compare comp = nullptr) {
if constexpr (std::is_same_v<Compare, void *>)
std::sort(std::begin(c), std::end(c));
else
std::sort(std::begin(c), std::end(c), comp);
return std::forward<Container>(c);
}
#endif
template<typename T> struct reversion_wrapper { T &iterable; };
template<typename T> auto begin(reversion_wrapper<T> w) {
using std::rbegin;
return rbegin(w.iterable);
}
template<typename T> auto end(reversion_wrapper<T> w) {
using std::rend;
return rend(w.iterable);
}
template<typename T> reversion_wrapper<T> rev_view(T &&iterable) {
return {std::forward<T>(iterable)};
}
/// @return nearest integer not less than the quotient x/y.
template<typename T, typename U> T qceil(T x, U y) {
assert(y > 0);
T q = x / y;
return q + (q * y < x);
}
/// @return nearest integer not greater than the quotient x/y.
template<typename T, typename U> T qfloor(T x, U y) {
assert(y > 0);
T q = x / y;
return q - (q * y > x);
}
template<typename T, typename U> std::pair<T, U> divmod(T x, U y) {
assert(y > 0);
T q = qfloor(x, y);
return {q, x - q * y};
};
/// @return nearest multiple of y not less than x.
template<typename T, typename U> T mceil(T x, U y) {
assert(y > 0);
return qceil(x, y) * y;
}
/// @return nearest multiple of y not greater than x.
template<typename T, typename U> T mfloor(T x, U y) {
assert(y > 0);
return qfloor(x, y) * y;
}
// recursive lambda: https://stackoverflow.com/a/40873657/6793559
#if __cplusplus >= 201703L
template<class F> struct y_combinator {
F f;
template<class... Args> decltype(auto) operator()(Args &&...args) {
return f(*this, std::forward<Args>(args)...);
}
};
template<class F> y_combinator(F) -> y_combinator<F>;
#endif
template<typename T> constexpr T INF = std::numeric_limits<T>::max() / 2;
/// @brief Usage: acc\<type_of_sum\>(array)
template<typename T, typename U> T acc(const U& array) {
return std::accumulate(std::begin(array), std::end(array), T(0));
}
template <typename T> T acc(const std::vector<T>& array) {
return std::accumulate(array.begin(), array.end(), T(0));
}
// maps values of a into 0, 1, 2, ..., preserving order.
template<typename T> std::vector<int> normalize(const std::vector<T> &a) {
assert(not a.empty());
int n = (int) a.size();
std::vector<int> I = argsort(a);
std::vector<int> b(a.size());
b[I[0]] = 0;
for (int i = 1; i < n; i++)
b[I[i]] = b[I[i - 1]] + (a[I[i - 1]] < a[I[i]]);
return b;
}
template<typename F, typename Int>
Int binary_search(F check, Int ok, Int ng, bool check_ok = true) {
if (check_ok)
assert(check(ok));
while (std::abs(ok - ng) > 1) {
Int x = ng + (ok - ng) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template<typename T, typename Int> int bit(T a, Int i) {
return a >> i & 1;
}
template <typename T, typename U>
std::vector<T> cumsum(const std::vector<U> &A, int off = 1) {
int N = A.size();
std::vector<T> B(N + 1);
for (int i = 0; i < N; i++) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
#define popcnt(x) __builtin_popcountll((x))
// sign used in principle of inclusion-exclusion
int pie_sign(int s) {
assert(s >= 0);
return popcnt(s) & 1 ? -1 : 1;
}
#endif// CP_UTILS
//
// Created by zjs on 2/19/25.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_TREE_BUILD_AUX_TREE_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_TREE_BUILD_AUX_TREE_HPP_
//
// Created by zjs on 2/22/24.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_LCA_TREE_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_LCA_TREE_HPP_
template<typename T = int>
struct lca_tree {
struct edge {
int from, to;
T weight;
};
bool ready = false;
std::vector<std::vector<int>> adj;
std::vector<edge> edges;
std::vector<int> pre;
std::vector<int> dep, num, sz, pv, pe, top, pos, order;
int rt;
lca_tree(int n)
: adj(n), dep(n), num(n, -1), sz(n), pv(n, -1), pe(n, -1), top(n),
pos(n, -1), rt(-1) {}
void add_edge(int u, int v, T weight = 1) {
int id = (int) edges.size();
adj[u].push_back(id);
adj[v].push_back(id);
edges.push_back({u, v, weight});
}
void dfs(int u) {
num[u] = (int) pre.size();
pre.push_back(u);
sz[u] = 1;
for (int id : adj[u]) {
if (id == pe[u])
continue;
int v = u ^ edges[id].from ^ edges[id].to;
// 易错点：计算dep[v]要在调用dfs(v)之前！
dep[v] = dep[u] + 1;
pv[v] = u;
pe[v] = id;
dfs(v);
sz[u] += sz[v];
}
}
void build(int root) {
rt = root;
dfs(root);
for (auto it = pre.rbegin(); it != pre.rend(); ++it) {
int u = *it;
if (pos[u] == -1) {
auto i = order.size();
while (1) {
pos[u] = (int) order.size();
order.push_back(u);
if (pv[u] == -1 || sz[u] * 2 < sz[pv[u]])// u is root or a light child
break;
u = pv[u];
}
while (i < order.size())
top[order[i++]] = u;
}
}
ready = true;
}
int lca(int u, int v) const {
assert(ready);
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]])
u = pv[top[u]];
else
v = pv[top[v]];
}
return dep[u] < dep[v] ? u : v;
}
// 返回点u的深度是depth的祖先
int ancesotr(int u, int depth) const {
assert(depth >= 0);
if (depth >= dep[u])
return u;
while (dep[top[u]] > depth)
u = pv[top[u]];
return order[pos[u] + dep[u] - depth];
}
};
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_LCA_TREE_HPP_
/// @param tree 原来的树
/// @param key_nodes 关键节点
/// @param init 初始化函数，格式是 void(int u)
/// @param link 连边函数，格式是 void(int u, int p)
template<typename T, typename F1, typename F2>
void build_aux_tree(const lca_tree<T> &tree, std::vector<int> key_nodes,
F1 init, F2 link, bool sorted = false) {
if (key_nodes.empty())
return;
assert(tree.ready);
if (!sorted)
std::sort(key_nodes.begin(), key_nodes.end(),
[&](int u, int v) { return tree.num[u] < tree.num[v]; });
std::vector<int> right_path;// 当前构建的虚树中最右边的一条链。
auto push = [&](int v) {
init(v);
right_path.push_back(v);
};
// 构建虚树
push(tree.rt);
for (int i = key_nodes[0] == tree.rt; i < (int) key_nodes.size(); i++) {
int w = tree.lca(key_nodes[i], right_path.back());
// 下面的 while 循环做的事情：
// right_path 里最后那一批，是 w 的严格后代的节点，
// 它们在虚树里的父节点已经确定。把这样的节点从 right_path 里移除。
while (tree.num[w] < tree.num[right_path.back()]) {
int v = right_path.back();
right_path.pop_back();
if (tree.num[right_path.back()] < tree.num[w])
push(w);
// 在虚树里v的父节点就是right_path.back()
link(v, right_path.back());
}
push(key_nodes[i]);
}
for (int i = (int) right_path.size() - 1; i > 0; i--)
link(right_path[i], right_path[i - 1]);
}
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_TREE_BUILD_AUX_TREE_HPP_
#include <utility>
using namespace io;
using namespace std;
const int maxn = 2e5 + 5;
vector<pair<int, int>> g[maxn];
map<int, int> cnt, sum;
long long ans = 0;
int n;
// 状态：
// cnt[x]：访问过的点中，距离点u极近的，权值是x的点的数量
// sum[x]：访问过的点中，距离点u极近的，权值是x的，不是点u祖先的点的 size 之和
int dfs(int u, int p, int s) {
ans += sum[s];
int sz = 1;
int old_cnt = cnt[s];
int old_sum = sum[s];
for (auto [v, w] : g[u])
if (v != p) {
cnt[s] = 1;
sum[s] = 0;
int sub_sz = dfs(v, u, s ^ w);
ans += (long long) (n - sub_sz) * (cnt[s] - 1);
sz += sub_sz;
}
ans += old_cnt * (long long) sz;
cnt[s] = old_cnt + 1;
sum[s] = old_sum + sz;
return sz;
}
void solve() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int a, b, c; cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
dfs(1, 0, 0);
cout << (long long) n * (n - 1) - ans << '\n';
}
#include <iostream>
int main() {
#if defined FILE_IO and not defined LOCAL
freopen(FILE_IO ".in", "r", stdin);
freopen(FILE_IO ".out", "w", stdout);
#endif
solve();
return 0;
}