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_{yin son(x)}dp[y][1])

(dp[x][1]=sum_{yin 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]))

我们发现，我们的只需要知道之前我们计算好贡献的儿子的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;
}