Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=2e5+7;
- int n;
- ll ans=0;
- int siz[N];
- int cnt[2];
- vector<int>G[N];
- void dfs(int x,int f,bool d){
- ++cnt[d];
- siz[x]=1;
- for(int i=0;i<G[x].size();++i){
- int v=G[x][i];
- if(v==f)continue;
- dfs(v,x,d^1);
- siz[x]+=siz[v];
- }
- ans+=(ll)siz[x]*(n-siz[x]);
- }
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- r(n);
- for(int i=1;i<n;++i){
- int u,v;r(u),r(v);
- G[u].push_back(v);
- G[v].push_back(u);
- }
- dfs(1,0,1);
- ans+=(ll)cnt[0]*cnt[1];
- ans>>=1;
- printf("%lld\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement