EOJ 3369. 三千米健身步道

3369. 三千米健身步道

题意

华师大是一个巨大的学校,众所周知,华师大的地图是一棵树,有 n 座教学楼,这些教学楼之间由 n−1 条道路相连,每条道路的长度都是一千米。
现在华师大投资建设一个「三千米健身步道」。为了让同学们不带喘气的跑(走)完这个健身步道,这个健身步道必须有一个起点,一个终点,中间是一段连续的三千米的跑道。华师大决定利用现有的 n−1 条道路建设这一个健身步道。问总共有多少种方案?

注意,起点和终点交换算同一种方案。

Input

第一行为 n (2≤n≤1000),表示教学楼数量,教学楼编号从 1 到 n。

接下来 n−1 行,每行为 ui,vi (1≤ui,vi≤n,ui≠vi),表示 ui,vi 之间有道路相连。

Output

输出方案数。如果不存在,输出 0。

样例
input
6
1 2
2 3
3 4
4 5
4 6
output
3

解法:虽说这题水吧,但是思维僵化了觉得所有的题目都应该是一遍dfs做的做不出来也是不应该的。做做水题开心一下。对每个点dfs计算最后除以2即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 10;
vector<int> g[maxn];
int n, cnt;
bool vis[maxn];
void dfs(int node, int f, int lay)
{
if(lay == 4)
{
cnt++; return;
}
for(auto idx: g[node])
if(idx != f)
dfs(idx, node, lay + 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++)
{
dfs(i, i, 1);
}

cout << (cnt >> 1)<< endl;
return 0;
}