Treepath 题解_牛客博客

一道简单的树形dp~

求路径长度为偶数的路径数量，我们可以转化为求路径长度模2等于0的路径数量，这样就好做了~

我们设 $dp[i][0]$ 表示i的子树中，到i的路径长度模2等于0的路径数量

同理， $dp[i][1]$ 就是模2等于1的路径数量了~

我们想想转移：

我们用 $x$ 的一个儿子 $y$ 来更新 $x$ ，那么，我们可以轻松发现，到 $y$ 的路径长度为奇数的，到 $x$ 就为偶数了（因为多走了一步）；到 $y$ 为偶数的，到 $x$ 就变成了奇数。所以，我们有转移方程：

$dp[x][0]=\sum_{y\in son(x)}dp[y][1]$

$dp[x][1]=\sum_{y\in son(x)}dp[y][0]$

好了，求出这个后，我们就来想想怎么求答案。

我们可以考虑枚举每个路径的lca，这样，我们发现，我们其实需要用的就是dp值了~

我们假设，我们现在枚举到的lca是 $x$ ，我们假设，我们现在添加了一个新的儿子 $y$ ,要算 $y$ 关于之前已添加点的贡献，怎么办？

首先，假设 $y$ 不与其他儿子合并，那么答案就是 $dp[y][1](到x要多走1步)$

如果 $y$ 和其他儿子合并呢？假设之前已经添加好并计算好贡献的儿子分别为 $a_1,a_2...a_k$

我们发现，答案就是:

$\sum_{i=1}^{k}(dp[a_i][0]*dp[y][0]+dp[a_i][1]*dp[y][1])$

我们把答案整理下，就是：

$dp[y][0]*\sum_{i=1}^{k}(dp[a_i][0])+dp[y][1]*(\sum_{i=1}^{k}(dp[a_i][1])+1)$

我们发现，我们的只需要知道之前我们计算好贡献的儿子的dp值的和即可直接获得现在这个儿子的贡献了

我们观察后发现，这个和，不就是我们dfs时，算的 $dp[x][1/0]$ 的值吗？所以，我们可以非常简单的在dfs算 $dp[x][0/1]$ ,同时计算答案~

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
#define int long long
struct node{
    int v,nex;
}t[N<<1];
int las[N],len;
int dp[N][2];
inline void add(int u,int v){
    t[++len]=(node){v,las[u]},las[u]=len;
}
long long ans;
inline void dfs(int now,int fa){
    dp[now][0]=1;
    for(int i=las[now];i;i=t[i].nex){
        int v=t[i].v;
        if(v!=fa){
            dfs(v,now);
            ans+=(dp[v][0]*dp[now][1]);ans+=(dp[v][1]*dp[now][0]);
            dp[now][0]+=dp[v][1];dp[now][1]+=dp[v][0];
        }
    }
}
signed main(){
    int n;
    scanf("%lld",&n);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,1);
    printf("%lld",ans);
    return 0;
}