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即可。

#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;
}