#include using namespace std; #include #include #include using namespace __gnu_pbds; typedef tree < int, // Key Type null_type, // Mapped type less, // Compare functor rb_tree_tag, // Tree tag: [rb_tree_tag|splay_tree_tag|ov_tree_tag] tree_order_statistics_node_update // Update policy > ordered_set; // Extra functions: find_by_order() and order_of_key() ordered_set C[200000]; int Set[200000]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector> Edges; for(int i = 2; i <= n; ++i) { int a, b; cin >> a >> b; Edges.emplace_back(a, b); } for(int i = 1; i <= n; ++i) { C[i].insert(i); Set[i] = i; } sort(Edges.begin(), Edges.end(), [](pair a, pair b) { return a.first + a.second < b.first + b.second; }); long long m = (1LL * n * (n - 1)) / 2; for(auto x : Edges) { if(C[Set[x.first]].size() > C[Set[x.second]].size()) swap(x.first, x.second); // cerr << "Edge: " << x.first << " " << x.second << endl; int now = x.first + x.second; // cerr << now << endl; for(auto node : C[Set[x.first]]) { // cerr << "Vars: " << node << endl; // Count less int cnt = C[Set[x.second]].order_of_key(now - node); // cerr << "- " << cnt << endl; m -= cnt; } for(auto node : C[Set[x.first]]) { C[Set[x.second]].insert(node); assert(Set[node] == Set[x.first]); Set[node] = Set[x.second]; } } cout << m << endl; return 0; }