CF690F1 Tree of Life (easy)

简要题意

给你一棵树，求树上长度为 $2$ 的路径条数

策略分析

我们看下面这张图：

我们发现对于点 $u,v$，$v$ 是与 $u$ 相连的一个点，从 $u$ 出发的长度为 $2$ 的路径条数就等于 $v$ 的度数减去 $1$，因为 $u$ 本身也和 $v$ 相连，所以要把自己减掉。比如说上面这张图中，与 $1$ 距离为 $2$ 的点有 $6,7,8,9,5$ 这 $5$ 个，而 $1$ 的三个子节点的度数分别为 $3,3,2$，分别减去 $1$ 再相加刚好是 $5$。

我们对这整张图统计以后，其实对于每一个点我们都统计了与它距离为 $2$ 的点，因为存图时是无向图，所以同一条路径一定计算了两次，累加的答案要减半。

时间复杂度 $O(n^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
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

namespace SHAWN {
    const int N = 1e4 + 7;
    vector<int> edge[N];
    int n, sum;
    int work()
    {
        cin >> n;
        for (int i = 1, x, y; i < n; ++i) {
            cin >> x >> y;
            edge[x].emplace_back(y);
            edge[y].emplace_back(x);
        }
        for (int i = 1; i <= n; ++i) {
            for (auto it : edge[i]) { 
                sum += edge[it].size() - 1; 
            }
        }
        sum >>= 1;
        cout << sum << '\n';
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

说些什么吧！

twikoo