#include #if __has_include() #endif using namespace std; #define eb emplace_back #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define RDVV(T,n,...) vec__VA_ARGS__;fe(refs(__VA_ARGS__),e)e.get().resizes(n);vin(__VA_ARGS__) #define VV(n,...) RDVV(ll,n,__VA_ARGS__) #define fo(i,...) for(auto[i,i##stop,i##step]=for_range(0,__VA_ARGS__);ivoid pp(const auto&...a){[[maybe_unused]]const char*c="";((o<(a...);} #define entry defpp void main();void main2();}int main(){my::io();my::main();}namespace my{ namespace my{ void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<constexpr auto for_range(T s,T b){T a=0;if(s)swap(a,b);return array{a-s,b,1-s*2};} void lin(auto&...a){(cin>>...>>a);} void vin(auto&...a){fo(i,(a.size()&...))(cin>>...>>a[i]);} void dec(auto&...a){((--a),...);} templateusing pack_back_t=tuple_element_t>; } namespace my{ templateconstexpr int depth=0; templatestruct core_t_helper{using type=T;}; templateusing core_t=core_t_helper::type; templatestruct vec; templatestruct hvec_helper{using type=vec::type>;}; templatestruct hvec_helper<0,T>{using type=T;}; templateusing hvec=hvec_helper::type; templatestruct vec:vector{ static constexpr int D=depth+1; using C=core_t; using vector::vector; void resizes(const auto&...a){if constexpr(sizeof...(a)==D)*this=make(a...,C{});else{ }} static auto make(ll n,const auto&...a){ if constexpr(sizeof...(a)==1)return vec(n,array{a...}[0]); else { } } vec&operator--(){fe(*this,e)--e;return*this;} ll size()const{return vector::size();} auto&emplace_back(auto&&...a){vector::emplace_back(std::forward(a)...);return*this;} }; templaterequires(sizeof...(A)>=2)vec(const A&...a)->vec>>; } namespace my{ templatestruct queue:std::queue{ queue()=default; queue(const initializer_list&a){fe(a,e)this->emplace(e);} ll size()const{return std::queue::size();} T pop(){T r=this->front();std::queue::pop();return r;} }; } namespace my{ templatestruct edge{ int from_,to_; WT wt_; int id_; edge()=default; edge(int from,int to,WT wt=1,int id=-1):from_(from),to_(to),wt_(wt),id_(id){} }; } namespace my{ templateclass RootedTree{ public: ll n_; vec>>edges_; vec>rev_edge_; int root_; RootedTree(ll n,ll r):n_(n),edges_(n),rev_edge_(n,{-1,-1,WT{},-1}),root_(r){} decltype(auto)operator[](ll i){return edges_[i];} ll size()const{return n_;} auto par(ll u)const{return u==root_?-1:rev_edge_[u].from_;} void set_edge(const edge&e){ edges_[e.from_].eb(e); rev_edge_[e.to_]=e; } auto subtree_size_enumerate()const{ vecres(size(),1); ef(bfs_order(root_),u)if(ll p=par(u);p!=-1)res[p]+=res[u]; return res; } auto bfs_order(ll start=-1)const{ if(start==-1)start=root_; vecord; queueq{start}; while(q.size()){ ll u=q.pop(); ord.eb(u); fe(edges_[u],e)q.emplace(e.to_); } return ord; } }; } namespace my{ templateclass Graph{ public: ll n_; vec>>edges_; Graph()=default; Graph(ll n):n_(n),edges_(n){} auto&add_edges(const vec&a,const vec&b){fo(i,a.size())edges_[a[i]].eb(a[i],b[i],1,i);return*this;} vecbuf; int count=0; auto bfs_tree(int s)const{ RootedTreetree(n_,s); vecused(n_); queue>q{{-1,s,WT{},-1}}; while(q.size()){ auto pu=q.pop(); auto u=pu.to_; if(used[u])continue; used[u]=1; if(pu.from_!=-1)tree.set_edge(pu); fe(edges_[u],e)if(!used[e.to_])q.emplace(e); } return tree; } }; } namespace my{entry void main(){ LL(N); VV(N-1,a,b);dec(a,b); Graphtmp(N); auto g=tmp.add_edges(a,b).add_edges(b,a).bfs_tree(0); auto sz=g.subtree_size_enumerate(); ll ans=0; fo(u,N){ ans+=sz[u]*(N-sz[u]); fe(g[u],e){ ans+=sz[e.to_]*(N-sz[e.to_]); } } pp(ans+N*N); }}