[每日一题]4.15 Treepath

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
struct node{
int t,nex;
};
node a[maxn<<1];
int head[maxn],tot,cnt[maxn];
void add(int x,int y){
  a[++tot].t = y,a[tot].nex = head[x],head[x] = tot;
}
void dfs(int x,int fa,int len)
{
  cnt[x] = len;
  for(int i=head[x]; i ; i=a[i].nex){
      if(a[i].t != fa)
          dfs(a[i].t , x , len + 1);
  }
}
int main()
{
  int n,x,y,cnt1 = 0 ,cnt2 = 0;
  cin>>n;
  for(int i=1;i<n;i++)
      cin>>x>>y,add(x,y),add(y,x);
  dfs(1 , 0 , 0);
  for(int i=1;i<=n;i++){
      if(cnt[i]%2)cnt1++;
      else cnt2++;
  }
  cout<<(1ll*cnt1*(cnt1 - 1)/2) + (1ll*cnt2*(cnt2 - 1)/2)<<endl;
  return 0;
}