Treepath（树形DP）

题目：

给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。1<=n<=100000

做法：

设1为根，树形DP求解。
设： $dp[u][0]$ 表示以 $u$ 为根的子树中结点 $v$ 到 $u$ 的路径为偶数的 $v$ 数量。 $dp[u][1]$ 表示以 $u$ 为根的子树中结点 $v$ 到 $u$ 的路径为奇数的 $v$ 数量。
树上所有路径可以视为经过根节点和不经过根节点两种。而不经过根节点的路径可以看成经过子树上根节点的情况。也就是说我们只需统计经过每棵子树根节点的路径就可以了。
经过根结点的偶数路径的数量 = 偶数 $v$ 配偶数 $v$ +奇数 $v$ 配奇数 $v$ 的情况。可以一边dfs一边求解。
请看代码。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
vector<int> g[N];
int dp[N][2];
ll ans;
void dfs(int u, int p){
    dp[u][0] = dp[u][1] = 0;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v == p) continue;
        dfs(v, u);
        int odd = dp[v][0]+1, even = dp[v][1];//从结点v的子树上来有odd个奇数路径，有even个偶数路径。
        ans += even+even*dp[u][0]+odd*dp[u][1];//统计经过u的偶数路径数量。
        dp[u][0] += even, dp[u][1] += odd;//更新
    }
}
int main(void){
    IOS;
    int n; cin >> n;
    for (int i = 0; i < n-1; ++i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ans = 0;
    dfs(1, 1);
    cout << ans << endl;
    return 0;
}