// #pragma GCC optimize("O3,unroll-loops") #include // #include using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif template struct graph{ using Weight_t = T; struct Edge_t{ int from, to; T cost; }; int n; vector edge; vector> adj; function ignore; graph(int n = 1): n(n), adj(n){ assert(n >= 1); } graph(const vector> &adj, bool undirected = true): n((int)adj.size()), adj(n){ assert(n >= 1); if(undirected){ for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v); } else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v); } graph(const vector>> &adj, bool undirected = true): n((int)adj.size()), adj(n){ assert(n >= 1); if(undirected){ for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w); } else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w); } graph(int n, vector> &edge, bool undirected = true): n(n), adj(n){ assert(n >= 1); for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v); } graph(int n, vector> &edge, bool undirected = true): n(n), adj(n){ assert(n >= 1); for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w); } int operator()(int u, int id) const{ #ifdef LOCAL assert(0 <= id && id < (int)edge.size()); assert(edge[id].from == u || edge[id].to == u); #endif return u ^ edge[id].from ^ edge[id].to; } int link(int u, int v, T w = {}){ // insert an undirected edge int id = (int)edge.size(); adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w}); return id; } int orient(int u, int v, T w = {}){ // insert a directed edge int id = (int)edge.size(); adj[u].push_back(id), edge.push_back({u, v, w}); return id; } void clear(){ for(auto [u, v, w]: edge){ adj[u].clear(); adj[v].clear(); } edge.clear(); ignore = {}; } graph transposed() const{ // the transpose of the directed graph graph res(n); for(auto &e: edge) res.orient(e.to, e.from, e.cost); res.ignore = ignore; return res; } int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule) return (int)adj[u].size(); } // The adjacency list is sorted for each vertex. vector> get_adjacency_list() const{ vector> res(n); for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){ if(ignore && ignore(id)) continue; res[(*this)(u, id)].push_back(u); } return res; } void set_ignoration_rule(const function &f){ ignore = f; } void reset_ignoration_rule(){ ignore = nullptr; } friend ostream &operator<<(ostream &out, const graph &g){ for(auto id = 0; id < (int)g.edge.size(); ++ id){ if(g.ignore && g.ignore(id)) continue; auto &e = g.edge[id]; out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n"; } return out; } }; // Requires graph template struct dfs_forest{ int n; T base_dist; vector dist; vector pv; vector pe; vector order; vector pos; vector end; vector size; vector root_of; vector root; vector depth; vector min_depth; vector min_depth_origin; vector min_depth_spanning_edge; // extra_edge[u]: adjacent edges of u which is not part of the spanning forest found during the last dfs-like run. vector> extra_edge; vector was; dfs_forest(T base_dist = 0): base_dist(base_dist){ } void init(int n){ this->n = n; pv.assign(n, -1); pe.assign(n, -1); order.clear(); pos.assign(n, -1); end.assign(n, -1); size.assign(n, 0); root_of.assign(n, -1); root.clear(); depth.assign(n, -1); min_depth.assign(n, -1); min_depth_origin.assign(n, -1); min_depth_spanning_edge.assign(n, -1); dist.assign(n, base_dist); extra_edge.assign(n, {}); was.assign(n, -2); attempt = -1; } int attempt; // O(# of nodes reachable from u) template> void _dfs(const graph &g, int u, F UT = plus<>()){ depth[u] = 0; dist[u] = base_dist; root_of[u] = u; root.push_back(u); pv[u] = pe[u] = -1; auto recurse = [&](auto self, int u)->void{ was[u] = attempt; pos[u] = (int)order.size(); order.push_back(u); size[u] = 1; min_depth[u] = depth[u]; min_depth_origin[u] = u; min_depth_spanning_edge[u] = -1; for(auto id: g.adj[u]){ if(id == pe[u] || g.ignore && g.ignore(id)) continue; int v = g(u, id); if(was[v] == attempt){ if(min_depth[u] > depth[v]){ min_depth[u] = depth[v]; min_depth_spanning_edge[u] = id; } if(pe[u] != id) extra_edge[u].push_back(id); continue; } depth[v] = depth[u] + 1; dist[v] = UT(g.edge[id].cost, dist[u]); pv[v] = u; pe[v] = id; root_of[v] = root_of[u]; self(self, v); size[u] += size[v]; if(min_depth[u] > min_depth[v]){ min_depth[u] = min_depth[v]; min_depth_origin[u] = min_depth_origin[v]; min_depth_spanning_edge[u] = min_depth_spanning_edge[v]; } } end[u] = (int)order.size(); }; recurse(recurse, u); } // O(# of nodes reachable from src) template> void dfs(const graph &g, const vector &src, F UT = plus<>()){ assert(g.n <= n); root.clear(), order.clear(); ++ attempt; for(auto u: src){ assert(0 <= u && u < g.n); if(was[u] != attempt) _dfs(g, u, UT); } } // O(n + m) template> void dfs_all(const graph &g, F UT = plus<>()){ assert(g.n <= n); root.clear(), order.clear(); ++ attempt; for(auto u = 0; u < g.n; ++ u) if(was[u] != attempt) _dfs(g, u, UT); } // Check if u is visited during the last dfs-like call. bool visited(int u) const{ assert(0 <= u && u < n); return was[u] == attempt; } // Check if u is an ancestor of v in some spanning tree. bool ancestor_of(int u, int v) const{ assert(visited(u) && visited(v)); return pos[u] <= pos[v] && end[v] <= end[u]; } // Check if any cycle is found during the last dfs-like call. // If must_contain_root = true, the sought cycle is forced to contain one of the root of the trees. template optional>> find_any_cycle(const graph &g, bool must_contain_root = false) const{ for(auto u: order) for(auto id: extra_edge[u]){ int v = g(u, id); if(!ancestor_of(v, u) || must_contain_root && root_of[v] != v) continue; vector cycle_edge; while(u != v) cycle_edge.push_back(pe[u]), u = pv[u]; reverse(cycle_edge.begin(), cycle_edge.end()); cycle_edge.push_back(id); return pair{v, cycle_edge}; } return {}; } }; int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n; cin >> n; graph g(n); for(auto i = 0; i < n - 1; ++ i){ int u, v; cin >> u >> v, -- u, -- v; g.link(u, v, 1); } dfs_forest df; df.init(n); df.dfs(g, {0}); vector> cnt(n); long long res = 0; for(auto u: df.order | ranges::views::reverse){ ++ cnt[u][0]; for(auto id: g.adj[u]){ if(id == df.pe[u]){ continue; } int v = g(u, id); res += 1LL * cnt[u][1] * cnt[v][1] + 1LL * cnt[u][1] * cnt[v][2] + 1LL * cnt[u][2] * cnt[v][1]; for(auto d = 0; d <= 2; ++ d){ cnt[u][d + 1] += cnt[v][d]; } } for(auto d = 1; d <= 3; ++ d){ res += cnt[u][d]; } } cout << res << "\n"; return 0; } /* */