【牛客每日一题】4.15Treepath题解（树上dfs/树形DP）

题目链接&＃xff1a;https://ac.nowcoder.com/acm/problem/14248
来源&＃xff1a;牛客网

题目描述

给定一棵n个点的树&＃xff0c;问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。
输入描述:
第一行一个数n表示点的个数&＃xff1b;接下来n-1行&＃xff0c;每行两个整数x&＃xff0c;y表示边&＃xff1b;保证输入数据形成一棵树&＃xff1b;1<&＃61;n<&＃61;100000
输出描述:
一行一个整数表示答案。

示例1

输入

3
1 2
1 3


输出

1


题目要求长度为偶数的路径数&＃xff0c;那么先用链式前向星建图&＃xff0c;然后从深度角度出发, 以 1 为根 dfs 求出全部深度

那么我们画个图观察一下&＃xff0c;发现偶数层到偶数层 距离为偶数
奇数到奇数层 距离距离也为偶数
那么我们求出奇数层节点为a, 偶数层节点个数为b
答案为排列组合&＃xff0c;$C(a,2)\&＃43;C(b,2)$
换成代码就是$(a-1)\ast a/2\&＃43;(b-1)\ast b/2$
时间复杂度
$O(n)$

#include
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l&＃43;r)/2
#define over(i,s,t) for(register long long i&＃61;s;i<&＃61;t;&＃43;&＃43;i)
#define lver(i,t,s) for(register long long i&＃61;t;i>&＃61;s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N&＃61;100007;
const ll INF&＃61;1e10&＃43;9;
const double EPS&＃61;1e-10;//-10次方约等于趋近为0
ll dep[N];
ll n,head[N],tot;
struct node
{ll v,nex;
}G[N<<1];
void add(ll u,ll v)
{G[&＃43;&＃43;tot].v&＃61;v;G[tot].nex&＃61;head[u];head[u]&＃61;tot;
}void dfs(ll u,ll fa)
{dep[u]&＃61;dep[fa]&＃43;1;for(ll i&＃61;head[u];i;i&＃61;G[i].nex){if(G[i].v&＃61;&＃61;fa)continue;dfs(G[i].v,u);}
}
int main()
{scanf("%lld",&n);over(i,1,n-1){ll x,y;scanf("%lld%lld",&x,&y);add(x,y);add(y,x);}dfs(1,0);ll a&＃61;0,b&＃61;0;over(i,1,n)if(dep[i]&1)a&＃43;&＃43;;else b&＃43;&＃43;;printf("%lld\n",ll(a*(a-1)/2)&＃43;ll(b*(b-1)/2));return 0;
}

还有一种树形DP我明天再写&＃xff0c;先睡了

附上官方题解&＃xff1a;
【每日一题】4月15日题目精讲