组合题6 个小题
已作答 0 / 6
1#include <iostream>2using namespace std;3 4const int maxn = 1000;5int n;6int fa[maxn], cnt[maxn];7 8int getRoot(int v) {9 if (fa[v] == v) return v;10 return getRoot(fa[v]);11}12 13int main() {14 cin >> n;15 for (int i = 0; i < n; ++i) {16 fa[i] = i;17 cnt[i] = 1;18 }19 int ans = 0;20 for (int i = 0; i < n - 1; ++i) {21 int a, b, x, y;22 cin >> a >> b;23 x = getRoot(a);24 y = getRoot(b);25 ans += cnt[x] * cnt[y];26 fa[x] = y;27 cnt[y] += cnt[x];28 }29 cout << ans << endl;30 return 0;31}若输入的 a 和 b 值均在 [0,n−1] 的范围内,则对于任意 0≤i<n 都有 1≤cnt[i]≤n ()