树形DP简单模板题树上路径计数

这是题目:

思路很简单啦，如果你学过树形dp的话，这个就是模板题哈哈，首先我们考虑二维dp数组dp[N][2],dp[i][0]代表以i为i为根节点且路径长度数为偶数的数量，dp[i][1]就是奇数的数量，递推方程就很简单的可以写出来了dp[father][0] += dp[son][1]+1,dp[father][1] += dp[son][0] AC代码:

```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
const int N=100005;
vector<int>pre[N];
int dp[N][2];
void dfs(int index,int father)
{
    for(int i = 0;i < pre[index].size();i++)
    {
        if(pre[index][i]==father)continue;
        int s = pre[index][i];
        dfs(s,index);
        dp[index][0]+=dp[s][1]+1;
        dp[index][1]+=dp[s][0];
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
        {
            pre[i].clear();
        }
        for(int i = 1;i <= n-1;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            pre[a].push_back(b);
            pre[b].push_back(a);
        }
        dfs(1,0);
        long long res = (long long)dp[1][0]*(dp[1][1]+1);
        cout << res << endl;
    }
}

最后

以上就是伶俐白猫为你收集整理的树形DP简单模板题树上路径计数的全部内容，希望文章能够帮你解决树形DP简单模板题树上路径计数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。