Submission #64773382

---

Source Code Expand

#ifndef IO_HPP
#define IO_HPP 1

#include <array>
#include <cstdint>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

namespace io {

void __read(char& c) { std::cin >> c; }
void __read(std::string& s) { std::cin >> s; }

template <typename T>
void __read_real(T& x) {
  std::string s;
  __read(s);
  x = std::stod(s);
}

template <typename T>
void __read_integer(T& x) {
  std::cin >> x;
}

void __read(int& x) { __read_integer(x); }
void __read(unsigned int& x) { __read_integer(x); }
void __read(long& x) { __read_integer(x); }
void __read(unsigned long& x) { __read_integer(x); }
void __read(long long& x) { __read_integer(x); }
void __read(unsigned long long& x) { __read_integer(x); }
void __read(double& x) { __read_real(x); }
void __read(long double& x) { __read_real(x); }

template <class U, class V>
void __read(std::pair<U, V>& p) {
  __read(p.first);
  __read(p.second);
}

template <size_t N = 0, typename T>
void __read_tuple(T& t) {
  if constexpr (N < std::tuple_size<T>::value) {
    auto& x = std::get<N>(t);
    __read(x);
    __read_tuple<N + 1>(t);
  }
}
template <class... T>
void __read(std::tuple<T...>& t) {
  __read_tuple(t);
}

template <size_t N = 0, typename T>
void __read(std::array<T, N>& a) {
  for (auto& x : a) {
    __read(x);
  }
}

template <class T>
void __read(std::vector<T>& v) {
  for (auto& x : v) {
    __read(x);
  }
}

void read() {}
template <class H, class... T>
void read(H& h, T&... t) {
  __read(h), read(t...);
}

void __write(const char c) { std::cout << c; }

void __write(const std::string s) {
  for (char c : s) {
    __write(c);
  }
}

void __write(const char* s) {
  size_t len = strlen(s);
  for (size_t i = 0; i < len; ++i) {
    __write(s[i]);
  }
}

template <typename T>
void __write_integer(T x) {
  std::cout << x;
}

template <typename T>
void __write_real(T x) {
  std::ostringstream oss;
  oss << std::fixed << std::setprecision(15) << double(x);
  std::string s = oss.str();
  __write(s);
}

void __write(int x) { __write_integer(x); }
void __write(unsigned int x) { __write_integer(x); }
void __write(long x) { __write_integer(x); }
void __write(unsigned long x) { __write_integer(x); }
void __write(long long x) { __write_integer(x); }
void __write(unsigned long long x) { __write_integer(x); }
void __write(double x) { __write_real(x); }
void __write(long double x) { __write_real(x); }

template <class U, class V>
void __write(const std::pair<U, V> p) {
  __write(p.first);
  __write(' ');
  __write(p.second);
}

template <size_t N = 0, typename T>
void __write_tuple(const T t) {
  if constexpr (N < std::tuple_size<T>::value) {
    if constexpr (N > 0) {
      __write(' ');
    }
    const auto x = std::get<N>(t);
    __write(x);
    __write_tuple<N + 1>(t);
  }
}
template <class... T>
void __write(std::tuple<T...> t) {
  __write_tuple(t);
}

template <class T, size_t S>
void __write(const std::array<T, S> a) {
  auto n = a.size();
  for (size_t i = 0; i < n; i++) {
    if (i) {
      __write(' ');
    }
    __write(a[i]);
  }
}

template <class T>
void __write(const std::vector<T> v) {
  auto n = v.size();
  for (size_t i = 0; i < n; i++) {
    if (i) {
      __write(' ');
    }
    __write(v[i]);
  }
}

template <class T>
void __write(const std::set<T> s) {
  __write(std::vector<T>{s.cbegin(), s.cend()});
}

template <class K, class V>
void __write(const std::map<K, V> m) {
  __write(std::vector<std::pair<K, V>>{m.cbegin(), m.cend()});
}

void write() { __write('\n'); }
template <class Head, class... Tail>
void write(Head&& head, Tail&&... tail) {
  __write(head);
  if (sizeof...(Tail)) {
    __write(' ');
  }
  write(std::forward<Tail>(tail)...);
}

}  // namespace io

#endif  // IO_HPP

#ifdef ONLINE_JUDGE
#include <bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

#include <bits/stdc++.h>
#include <atcoder/all>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using namespace atcoder;
using namespace io;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<int> eccentricity(const vector<vector<int>>& g) {
  const int n = g.size();
  vector<int> height(n), answer(n);

  auto dfs = [&](auto&& self, int u, int p) -> void {
    height[u] = 0;
    for (int v : g[u]) {
      if (v == p) {
        continue;
      }
      self(self, v, u);
      height[u] = max(height[u], height[v] + 1);
    }
  };

  auto reroot = [&](auto&& self, int u, int p, int height_p) -> void {
    answer[u] = max(height[u], height_p);
    int m1{height_p}, m2{-1};

    for (int v : g[u]) {
      if (v == p) {
        continue;
      }
      const int candidate{height[v] + 1};
      if (candidate > m1) {
        m2 = m1;
        m1 = candidate;
      } else if (candidate > m2) {
        m2 = candidate;
      }
    }

    for (int v : g[u]) {
      if (v == p) {
        continue;
      }
      const int candidate{height[v] + 1};
      if (candidate == m1) {
        self(self, v, u, m2 + 1);
      } else {
        self(self, v, u, m1 + 1);
      }
    }
  };

  dfs(dfs, 0, -1);
  reroot(reroot, 0, -1, 0);
  return answer;
}

void solve() {
  int n1;
  read(n1);
  vector<pair<int, int>> uv1(n1 - 1);
  read(uv1);
  int n2;
  read(n2);
  vector<pair<int, int>> uv2(n2 - 1);
  read(uv2);
  vector<vector<int>> g1(n1), g2(n2);
  for (auto& [u, v] : uv1) {
    --u, --v;
    g1[u].push_back(v);
    g1[v].push_back(u);
  }
  for (auto& [u, v] : uv2) {
    --u, --v;
    g2[u].push_back(v);
    g2[v].push_back(u);
  }
  const auto ecc1{eccentricity(g1)}, ecc2{eccentricity(g2)};
  int m{max(*max_element(ecc1.cbegin(), ecc1.cend()),
            *max_element(ecc2.cbegin(), ecc2.cend()))};
  vector<long long> a(n1), b(n2);
  for (int e1 : ecc1) {
    ++a[e1];
  }
  for (int e2 : ecc2) {
    ++b[e2];
  }
  const auto c{convolution_ll(a, b)};
  int64_t answer{};
  for (int k{}; k < int(c.size()); ++k) {
    answer += c[k] * max(k + 1, m);
  }
  write(answer);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

Submission Info

Judge Result