solution

枚举起点和终点的LCA,然后将他们两两组合即可。

具体的,设f[i][0/1]表示以i为根的子树中,与根节点i的距离为偶数(0)奇数(1)的点的数量。

转移显然就是

然后考虑统计答案,以的两个节点,肯定不能在的同一个儿子里,所以转移的过程中,表示已经当前已经计算过得儿子造成的贡献,对于一个新的儿子

code

/*
* @Author: wxyww
* @Date: 2020-04-14 11:33:18
* @Last Modified time: 2020-04-14 11:39:50
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;
}e[N << 1];
int head[N],ejs;
ll f[N][2];
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
ll ans = 0;
void dfs(int u,int fa) {
    f[u][0] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v,u);
        ans += f[v][1] * f[u][0];
        ans += f[v][0] * f[u][1];
        f[u][0] += f[v][1];
        f[u][1] += f[v][0];
    }

}
int main() {
    int n = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}