Java(javac 1.8) 解法, 执行用时: 823ms, 内存消耗: 37924K, 提交时间: 2019-05-11 20:07:36

import java.util.Scanner;


public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] datas = new int[n+1];
		int i = 0,u,v,even = 1,odd = 0;
		long result = 0;
		while(++i < n){
			u = in.nextInt();
			v = in.nextInt();
			datas[v] = datas[u]+1;
			result += datas[v]%2==0?even++:odd++;
		}
		System.out.println(result);
	}

}

Python3 解法, 执行用时: 401ms, 内存消耗: 22300K, 提交时间: 2021-05-29 00:06:56

import sys
sys.setrecursionlimit(100000)

n = int(input())
g = [[] for _ in range(n)]
c = [0] * n
for _ in range(n - 1):
	u, v = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)

def dfs(u, p, x):
	c[u] = x
	for v in g[u]:
		if v != p: dfs(v, u, x ^ 1)
dfs(0, -1, 0)
x = sum(c)
ans = x * (x - 1) // 2 + (n - x) * (n - x - 1) // 2
print(ans)

C++14(g++5.4) 解法, 执行用时: 110ms, 内存消耗: 1920K, 提交时间: 2019-05-07 19:05:38

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int dep[200005];
int main()
{
    LL n,a,b,even = 1,odd = 0,res = 0;
    cin >> n;
    n--;
    while(n--)
    {
        cin >> a >> b;
        dep[b] = dep[a] + 1;
        res += dep[b] % 2 ? odd++ : even++;
    }
    cout << res<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 75ms, 内存消耗: 2364K, 提交时间: 2020-03-01 15:03:52

#include<bits/stdc++.h>
using namespace std;
long long dp[100005],n,x,y,u,v,ans;
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		dp[v]=dp[u]+1;
		ans+=dp[v]&1?x++:++y;
	}
	cout<<ans<<endl;
	return 0;
}