原题链接
题解
看清楚题目,是三个人都坐在同一辆校车!!
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> G[200005];
ll depth[200005]={0};
void dfs(ll now,ll fa)
{for(auto next:G[now]){if(next==fa) continue;depth[next]=depth[now]+1;dfs(next,now);}
}ll C(ll a,ll b)
{ll sum=1;for(ll i=0;i<b;i++){sum=sum*(a-i);}for(ll i=2;i<=b;i++) sum=sum/i;return sum;
}
int main()
{ll n;cin>>n;for(ll i=1;i<n;i++){ll x,y;cin>>x>>y;G[x].push_back(y);G[y].push_back(x);}dfs(1,0);ll cnt=0;for(ll i=1;i<=n;i++){if(depth[i]>=2) cnt+=C(depth[i],2);}cout<<C(n,3)-cnt;return 0;
}