Treepath
题目描述
给定一棵n个点的树,问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。
输入描述:
第一行一个数n表示点的个数;接下来n-1行,每行两个整数x,y表示边;保证输入数据形成一棵树;1<=n<=100000
输出描述:
一行一个整数表示答案。
示例1
输入
3
1 2
1 3
输出
1dfs,假设1为最顶层,遍历每一个节点,求出奇数层和偶数层的数量。
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define ll long long
4 const int N = 100010;
5 vector<int> vs[N];
6 bool vis[N];
7 ll ans1, ans2;
8 void dfs(int x, int de) {
9 vis[x] = true;
10 for(int i = 0; i < vs[x].size(); i ++) {
11 int v = vs[x][i];
12 if(!vis[v]) {
13 if((de+1) %2) ans1 ++;
14 else ans2 ++;
15 dfs(v, de+1);
16 }
17 }
18 }
19 void init(){
20 ans1 = ans2 = 0;
21 memset(vis, false, sizeof(vis));
22 for(int i = 1; i < N; i ++) vs[i].clear();
23 }
24 int main() {
25 int n, x, y;
26 while(scanf("%d", &n)!=EOF) {
27 init();
28 for(int i = 1; i < n; i ++) {
29 scanf("%d %d", &x, &y);
30 vs[x].push_back(y);
31 vs[y].push_back(x);
32 }
33 dfs(1, 1);
34 ans1++;
35 // printf("%d %d\n", ans1, ans2);
36 ll cnt = (ans1-1)*ans1 + (ans2-1)*ans2;
37 printf("%lld\n",cnt/2);
38 }
39 return 0;
40 }
原文链接: https://www.cnblogs.com/xingkongyihao/p/7668608.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/261292
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!