#include using namespace std; inline namespace IO { #define SFINAE(x, ...) \ template struct x : std::false_type {}; \ template struct x> : std::true_type {} SFINAE(DefaultI, decltype(std::cin >> std::declval())); SFINAE(DefaultO, decltype(std::cout << std::declval())); SFINAE(IsTuple, typename std::tuple_size::type); SFINAE(Iterable, decltype(std::begin(std::declval()))); template struct Reader { template void Impl(T &t) { if constexpr (DefaultI::value) is >> t; else if constexpr (Iterable::value) { for (auto &x : t) Impl(x); } else if constexpr (IsTuple::value) { std::apply([this](auto &...args) { (Impl(args), ...); }, t); } else static_assert(IsTuple::value, "No matching type for read"); } template void read(Ts &...ts) { ((Impl(ts)), ...); } }; template void re(Ts &...ts) { Reader{}.read(ts...); } #define def(t, args...) \ t args; \ re(args); template struct Writer { string comma() const { return debug ? "," : ""; } template constexpr char Space(const T &) const { return print_nd && (Iterable::value or IsTuple::value) ? '\n' : ' '; } template void Impl(T const &t) const { if constexpr (DefaultO::value) os << t; else if constexpr (Iterable::value) { if (debug) os << '{'; int i = 0; for (auto &&x : t) ((i++) ? (os << comma() << Space(x), Impl(x)) : Impl(x)); if (debug) os << '}'; } else if constexpr (IsTuple::value) { if (debug) os << '('; std::apply( [this](auto const &...args) { int i = 0; (((i++) ? (os << comma() << " ", Impl(args)) : Impl(args)), ...); }, t); if (debug) os << ')'; } else static_assert(IsTuple::value, "No matching type for print"); } template void ImplWrapper(T const &t) const { if (debug) os << "\033[0;31m"; Impl(t); if (debug) os << "\033[0m"; } template void print(Ts const &...ts) const { ((Impl(ts)), ...); } template void print_with_sep(const std::string &sep, F const &f, Ts const &...ts) const { ImplWrapper(f), ((os << sep, ImplWrapper(ts)), ...), os << '\n'; } void print_with_sep(const std::string &) const { os << '\n'; } }; template void pr(Ts const &...ts) { Writer{}.print(ts...); } template void ps(Ts const &...ts) { Writer{}.print_with_sep(" ", ts...); } } // namespace IO inline namespace Debug { template void err(Args... args) { Writer{}.print_with_sep(" | ", args...); } template void errn(Args... args) { Writer{}.print_with_sep(" | ", args...); } void err_prefix(string func, int line, string args) { cerr << "\033[0;31m\u001b[1mDEBUG\033[0m" << " | " << "\u001b[34m" << func << "\033[0m" << ":" << "\u001b[34m" << line << "\033[0m" << " - " << "[" << args << "] = "; } #ifdef LOCAL #define dbg(args...) err_prefix(__FUNCTION__, __LINE__, #args), err(args) #define dbgn(args...) err_prefix(__FUNCTION__, __LINE__, #args), errn(args) #else #define dbg(...) #define dbgn(args...) #endif const auto beg_time = std::chrono::high_resolution_clock::now(); // https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1 double time_elapsed() { return chrono::duration(std::chrono::high_resolution_clock::now() - beg_time) .count(); } } // namespace Debug inline namespace FileIO { void setIn(string s) { freopen(s.c_str(), "r", stdin); } void setOut(string s) { freopen(s.c_str(), "w", stdout); } void setIO(string s = "") { cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams cout << fixed << setprecision(12); // cin.exceptions(cin.failbit); // throws exception when do smth illegal // ex. try to read letter into int if ((int)(s.size())) setIn(s + ".in"), setOut(s + ".out"); // for old USACO } } // namespace FileIO #ifdef LOCAL #include #else #define debug(...) 42 #endif // LOCAL struct ChronoTimer { std::chrono::high_resolution_clock::time_point st; ChronoTimer() { reset(); } void reset() { st = std::chrono::high_resolution_clock::now(); } std::chrono::milliseconds::rep elapsed() { auto ed = std::chrono::high_resolution_clock::now(); return std::chrono::duration_cast(ed - st) .count(); } }; constexpr bool TEST = false; namespace std { template class y_combinator_result { Fun fun_; public: template explicit y_combinator_result(T &&fun) : fun_(std::forward(fun)) {} template decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward(args)...); } }; template decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result>(std::forward(fun)); } } // namespace std void run_case(int tc) { using ll = int64_t; def(int, N); vector> adj(N); for (int i = 0; i < N - 1; i++) { def(int, u, v); u--, v--; adj[u].push_back(v); adj[v].push_back(u); } vector dep(N), parent(N), ord(N); int ptr = 0; std::y_combinator([&](auto self, int u, int par) -> void { ord[ptr++] = u; for (auto &v : adj[u]) if (v != par) { dep[v] = dep[u] + 1; self(v, u); parent[v] = u; } })(0, -1); array _{}; vector> dp(N, _); for (int i = N - 1; i >= 0; i--) { int u = ord[i]; for (auto &v : adj[u]) if (v != parent[u]) { for (int j = 0; j < 3; j++) { dp[u][j + 1] += dp[v][j]; } } dp[u][0]++; } ll ans = 0; for (int i = 0; i < N; i++) { int cur = i; for (int d = 0; d <= 3; d++) { if (!cur) { for (int j = 0; j < 4 - d; j++) { ans += dp[cur][j]; } break; } ans += dp[cur][3 - d]; if (d == 3) { break; } ans += dp[cur][2 - d]; cur = parent[cur]; } } ans -= N; ans /= 2; ps(ans); } int main(int, char **) { #ifdef LOCAL ChronoTimer chrono; setIO("../src/prob"); #else setIO(); #endif int T = 1; if constexpr (TEST) re(T); for (int tc = 1; tc <= T; tc++) run_case(tc); #ifdef LOCAL ps("\nRunning Time:", chrono.elapsed(), "ms"); #endif }