每日一题 TreePath 树形dp+合并

Treepath

https://ac.nowcoder.com/acm/problem/14248

链接：https://ac.nowcoder.com/acm/problem/14248
来源：牛客网

Treepath

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

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

输入描述:

第一行一个数n表示点的个数；
接下来n-1行，每行两个整数x，y表示边；
保证输入数据形成一棵树；
1<=n<=100000

输出描述:

一行一个整数表示答案。

示例1

输入

复制 3 1 2 1 3

3
1 2
1 3

输出

复制 1

求偶数长度的路径有多少条

首先将题目转换一下：求点数为奇数的路径有多少条

然后将奇数的路径分为，从每个结点出发向下的奇数的路径与向上的奇数路径，向上的奇数路径就可以根据合并的思想，将每个节点作为中间节点过度一下即可：

具体使用

dp[i][1]表示从i出发，长度为奇数个点的路径数

dp[i][0]表示从i出发，长度为偶数个点的路经数

转移显然：

dp[u][1]+=dp[e][0] ///当前节点作为一个点

dp[u][0]+=dp[e][1]

中间启发合并过度节点只需要记录在访问节点前的偶数节点个数与奇数节点个数即可：

Code：

/*** keep hungry and calm CoolGuang!***/
//#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int maxn=3e5+6;
const int mod=20020421;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll dp[maxn][2];
ll ans=0;
vector<int>v[maxn];
void dfs(int u,int fa){
    dp[u][1]=1;
    ll a=0,b=0;
    for(int e:v[u]){
        if(e==fa) continue;
        dfs(e,u);
        dp[u][1]+=dp[e][0];
        dp[u][0]+=dp[e][1];
        ans+=dp[e][0]*a;
        ans+=dp[e][1]*b;
        a+=dp[e][0];
        b+=dp[e][1];
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++)
        ans+=dp[i][1];
    printf("%lld\n",ans-n);
    return 0;
}

/***
1 2 3 4 5
***/