每日一题 TreePath 树形dp+合并
Treepath
https://ac.nowcoder.com/acm/problem/14248
链接：https://ac.nowcoder.com/acm/problem/14248
来源：牛客网
Treepath
求偶数长度的路径有多少条
首先将题目转换一下：求点数为奇数的路径有多少条
然后将奇数的路径分为，从每个结点出发向下的奇数的路径与向上的奇数路径，向上的奇数路径就可以根据 合并的思想，将每个节点作为中间节点过度一下即可：
具体使用
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
***/
速腾聚创二面26人在聊
查看30道真题和解析
投递拓竹科技等公司10个岗位