Solution

题目讲的比较明白，目的明确。就是每条边边权为1，求长为偶数的路径数。
我们知道 奇数+奇数=偶数；奇数+偶数=奇数；偶数+偶数=偶数；与异或运算比较相似。
我们用 记录以i为根节点的0代表偶数边数，1代表奇数边数。
那么我们知道，叶子节点的偶数路径有一条0，奇数路径没有。
所以我们可以推出状态转移方程
因为存在一条连向父节点的边，所以子节点只可以选择奇偶性不同的路径数相加。
得到上面递推式，我们在考虑更新答案，对于每个待处理父节点，已得到的偶数边*未处理过的子节点奇数边，或者奇偶互换，最终求和即得到最终偶数边个数。

时间复杂度 O(N)

Code:

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7;
vector<int>    e[N];
ll dp[N][2]; //0代表以i为根，偶数长度的边数，1代表奇数长度的边数
int n;
ll ans;

void dfs(int x, int fa) {
    dp[x][0] = 1; //初始化长度0为偶数的边有一条
    for (auto it : e[x]) {
        if (it == fa)    continue;
        dfs(it, x);
        ans += dp[x][0] * dp[it][1]; //以父节点被计算过的偶数边*未计算过的子节点奇数边（考虑连接父节点一条边）和为偶数，更新ans
        ans += dp[x][1] * dp[it][0]; //以父节点被计算过的奇数边*未计算过的子节点偶数边（考虑连接父节点一条边）和为偶数，更新ans
        dp[x][0] += dp[it][1];  //子节点奇数边+连接父节点边=偶数边合计父节点中
        dp[x][1] += dp[it][0];  //子节点偶数边+连接父节点边=奇数边合计父节点中
    }
}

int main() {
    n = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        e[u].push_back(v); //建树
        e[v].push_back(u); 
    }
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}