結果
| 問題 |
No.3193 Submit Your Solution
|
| ユーザー |
|
| 提出日時 | 2025-06-27 22:07:58 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,389 bytes |
| コンパイル時間 | 7,617 ms |
| コンパイル使用メモリ | 356,556 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-06-27 22:08:18 |
| 合計ジャッジ時間 | 19,651 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | TLE * 1 -- * 16 |
ソースコード
#pragma GCC optimize("Ofast,unroll-loops")
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using namespace atcoder;
using mint = modint998244353;
#define rep1(i, r) for (int i = 0; i < (int)(r); ++i)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); ++i)
#define rep3(i, l, r, d) for (int i = (l); i < (int)(r); i += (d))
#define rep_r1(i, r) for (int i = (r) - 1; i >= 0; --i)
#define rep_r2(i, l, r) for (int i = (r) - 1; i >= (l); --i)
#define rep_r3(i, l, r, d) for (int i = (r) - 1; i >= (l); i -= (d))
#define fifth(a, b, c, d, e, ...) e
#define rep(...) fifth(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rep_r(...) fifth(__VA_ARGS__, rep_r3, rep_r2, rep_r1)(__VA_ARGS__)
template <typename... T> void in(T &...args) { (cin >> ... >> args); }
template <typename... T> void in_z(T &...args) {
(cin >> ... >> args);
(..., --args);
}
#define in_d(type, ...) \
type __VA_ARGS__; \
in(__VA_ARGS__)
#define in_dz(type, ...) \
type __VA_ARGS__; \
in_z(__VA_ARGS__)
template <typename It> void in_i(It first, It last) {
for (It it = first; it != last; ++it) {
in(*it);
}
}
template <typename It> void in_iz(It first, It last) {
for (It it = first; it != last; ++it) {
in(*it);
--*it;
}
}
template <int N> struct str_literal {
static constexpr int length = N - 1;
char buf[N];
constexpr str_literal(const char (&s_literal)[N]) {
rep(i, N) { buf[i] = s_literal[i]; }
buf[length] = '\0';
}
};
template <int N> ostream &operator<<(ostream &os, const str_literal<N> &str) {
os << str.buf;
return os;
}
template <str_literal tail = "\n", bool do_flush = false> void out() {
cout << tail;
if (do_flush) {
cout << flush;
}
}
template <str_literal split = " ", str_literal tail = "\n",
bool do_flush = false, typename Hd, typename... Tl>
void out(const Hd &hd, const Tl &...tl) {
cout << hd;
if constexpr (sizeof...(Tl)) {
(cout << ... << (cout << split, tl));
}
cout << tail;
if (do_flush) {
cout << flush;
}
}
template <str_literal split = " ", str_literal tail = "\n",
bool do_flush = false, typename It>
void out_i(It first, It last) {
for (It it = first; it != last; ++it) {
if (it != first) {
cout << split;
}
cout << *it;
}
cout << tail;
if (do_flush) {
cout << flush;
}
}
template <str_literal tail = "\n", bool do_flush = false> void err() {
cerr << tail;
if (do_flush) {
cout << flush;
}
}
template <str_literal split = " ", str_literal tail = "\n",
bool do_flush = false, typename Hd, typename... Tl>
void err(const Hd &hd, const Tl &...tl) {
cerr << hd;
if constexpr (sizeof...(Tl)) {
(cerr << ... << (cerr << split, tl));
}
cerr << tail;
if (do_flush) {
cout << flush;
}
}
template <str_literal split = " ", str_literal tail = "\n",
bool do_flush = false, typename It>
void err_i(It first, It last) {
for (It it = first; it != last; ++it) {
if (it != first) {
cerr << split;
}
cerr << *it;
}
cerr << tail;
if (do_flush) {
cout << flush;
}
}
#define dir(dx, dy) for (auto [dx, dy] : {pair{1, 0}, {0, 1}, {-1, 0}, {0, -1}})
#define dir_8(dx, dy) \
for (auto [dx, dy] : {pair{1, 0}, \
{1, 1}, \
{0, 1}, \
{-1, 1}, \
{-1, 0}, \
{-1, -1}, \
{0, -1}, \
{1, -1}})
#define all(v) (v).begin(), (v).end()
#define all_r(v) (v).rbegin(), (v).rend()
#define dedup(v) (v).erase(unique(all(v)), (v).end())
#define yn(b) ((b) ? "Yes" : "No")
template <typename T1, typename T2> bool chmin(T1 &l, const T2 &r) {
if (r < l) {
l = r;
return true;
}
return false;
}
template <typename T1, typename T2> bool chmax(T1 &l, const T2 &r) {
if (r > l) {
l = r;
return true;
}
return false;
}
template <typename Hd1, typename Hd2, typename... Tl>
auto min_of(Hd1 hd1, Hd2 hd2, Tl... tl) {
if constexpr (sizeof...(Tl) == 0) {
return min(hd1, hd2);
} else {
return min(hd1, min_of(hd2, tl...));
}
}
template <typename Hd1, typename Hd2, typename... Tl>
auto max_of(Hd1 hd1, Hd2 hd2, Tl... tl) {
if constexpr (sizeof...(Tl) == 0) {
return max(hd1, hd2);
} else {
return max(hd1, max_of(hd2, tl...));
}
}
template <typename Hd1, typename Hd2, typename... Tl>
auto gcd_of(Hd1 hd1, Hd2 hd2, Tl... tl) {
if constexpr (sizeof...(Tl) == 0) {
return gcd(hd1, hd2);
} else {
return gcd(hd1, gcd_of(hd2, tl...));
}
}
template <typename Hd1, typename Hd2, typename... Tl>
auto lcm_of(Hd1 hd1, Hd2 hd2, Tl... tl) {
if constexpr (sizeof...(Tl) == 0) {
return lcm(hd1, hd2);
} else {
return lcm(hd1, lcm_of(hd2, tl...));
}
}
template <typename T, size_t N>
auto make_vector(vector<size_t> &sizes, T const &x) {
if constexpr (N == 1) {
return vector(sizes[0], x);
} else {
size_t size = sizes[N - 1];
sizes.pop_back();
return vector(size, make_vector<T, N - 1>(sizes, x));
}
}
template <typename T, size_t N>
auto make_vector(size_t const (&sizes)[N], T const &x = T()) {
vector<size_t> s(N);
rep(i, N) { s[i] = sizes[N - i - 1]; }
return make_vector<T, N>(s, x);
}
template <typename T, size_t N>
auto make_vector(vector<int> &sizes, T const &x) {
if constexpr (N == 1) {
return vector(sizes[0], x);
} else {
int size = sizes[N - 1];
sizes.pop_back();
return vector(size, make_vector<T, N - 1>(sizes, x));
}
}
template <typename T, size_t N>
auto make_vector(int const (&sizes)[N], T const &x = T()) {
vector<int> s(N);
rep(i, N) { s[i] = sizes[N - i - 1]; }
return make_vector<T, N>(s, x);
}
template <typename T, size_t Hd, size_t... Tl> auto make_array() {
if constexpr (sizeof...(Tl) == 0) {
return array<T, Hd>{};
} else {
return array<decltype(make_array<T, Tl...>()), Hd>{};
}
}
constexpr int inf32 = 1'000'000'001;
constexpr ll inf64 = 2'000'000'000'000'000'001;
constexpr ll ten_powers[19] = {1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000,
10000000000,
100000000000,
1000000000000,
10000000000000,
100000000000000,
1000000000000000,
10000000000000000,
100000000000000000,
1000000000000000000};
template <typename S, S e> constexpr S e_const() { return e; }
template <typename S1, S1 e1, typename S2, S2 e2>
constexpr pair<S1, S2> e_pair() {
return {e1, e2};
}
template <typename S> S op_min(S a, S b) { return min(a, b); }
template <typename S> S op_max(S a, S b) { return max(a, b); }
template <typename S> S op_add(S a, S b) { return a + b; }
template <typename S1, typename S2>
pair<S1, S2> op_add_pair(pair<S1, S2> a, pair<S1, S2> b) {
auto [a1, a2] = a;
auto [b1, b2] = b;
return {a1 + b1, a2 + b2};
}
template <typename F1, typename F2, typename S>
S mapping_affine(pair<F1, F2> f, S x) {
auto [a, b] = f;
return a * x + b;
}
template <typename F1, typename F2, typename S1, typename S2>
pair<S1, S2> mapping_len_and_affine(pair<F1, F2> f, pair<S1, S2> x) {
auto [a, b] = f;
auto [x1, x2] = x;
return {x1, a * x2 + b * x1};
}
template <typename F1, typename F2>
pair<F1, F2> composition_affine(pair<F1, F2> f, pair<F1, F2> g) {
auto [a_f, b_f] = f;
auto [a_g, b_g] = g;
return {a_f * a_g, a_f * b_g + b_f};
}
template <typename S, S e>
using segtree_min = segtree<S, op_min<S>, e_const<S, e>>;
template <typename S, S e>
using segtree_max = segtree<S, op_max<S>, e_const<S, e>>;
template <typename S> using segtree_add = segtree<S, op_add<S>, e_const<S, 0>>;
template <typename S, S e>
using lazy_segtree_min =
lazy_segtree<S, op_min<S>, e_const<S, e>, pair<S, S>,
mapping_affine<S, S, S>, composition_affine<S, S>,
e_pair<S, 1, S, 0>>;
template <typename S, S e>
using lazy_segtree_max =
lazy_segtree<S, op_max<S>, e_const<S, e>, pair<S, S>,
mapping_affine<S, S, S>, composition_affine<S, S>,
e_pair<S, 1, S, 0>>;
template <typename S>
using lazy_segtree_add =
lazy_segtree<pair<int, S>, op_add_pair<int, S>, e_pair<int, 0, S, 0>,
pair<S, S>, mapping_len_and_affine<S, S, int, S>,
composition_affine<S, S>, e_pair<S, 1, S, 0>>;
using u64 = unsigned long long;
int main(void) {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(15);
in_d(int, n);
vector<int> u(n - 1);
auto v = u;
auto x = u;
auto y = u;
vector<vector<int>> g_1(n);
auto g_2 = g_1;
rep(i, n - 1) {
in_z(u[i], v[i]);
g_1[u[i]].emplace_back(v[i]);
g_1[v[i]].emplace_back(u[i]);
}
rep(i, n - 1) {
in_z(x[i], y[i]);
g_2[x[i]].emplace_back(y[i]);
g_2[y[i]].emplace_back(x[i]);
}
u64 ans = 0;
vector<int> dist_1(n, -1);
vector<int> dist_2(n, -1);
rep(i, n) {
fill(all(dist_1), -1);
fill(all(dist_2), -1);
dist_1[i] = 0;
dist_2[i] = 0;
stack<int> s;
s.emplace(i);
while (!s.empty()) {
int v = s.top();
s.pop();
for (int u : g_1[v]) {
if (dist_1[u] == -1) {
dist_1[u] = dist_1[v] + 1;
s.emplace(u);
}
}
}
s.emplace(i);
while (!s.empty()) {
int v = s.top();
s.pop();
for (int u : g_2[v]) {
if (dist_2[u] == -1) {
dist_2[u] = dist_2[v] + 1;
s.emplace(u);
}
}
}
rep(j, n) {
if (dist_1[j] != -1 && dist_2[j] != -1) {
ans += u64(dist_1[j]) * dist_2[j];
}
}
}
out(ans);
return 0;
}