思路

  此题直接使用暴力求解，在建树之后，对于每一个点计算它的子节点的个数，并用map表记录下来，对于拥有同一个个数子节点的节点，记数量为m，相互之间的组合数量即为C(m,2)，即m*(m-1)/2

代码

python

T = int(input())
while T > 0:
    T -= 1
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)
    
    mapp = {}
    for u in range(n):
        cnt = len(g[u]) - 1
        if u == 0:
            cnt += 1
        mapp[cnt] = mapp.get(cnt, 0) + 1
    
    ans = 0
    for k, v in mapp.items():
        ans += v * (v - 1) // 2
    
    print(ans)

c++

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int T;
    cin >> T;

    while (T > 0) {
        T--;

        int n;
        cin >> n;

        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            g[u - 1].push_back(v - 1);
            g[v - 1].push_back(u - 1);
        }

        unordered_map<int, int> mapp;
        for (int u = 0; u < n; u++) {
            int cnt = g[u].size() - 1;
            if (u == 0) {
                cnt += 1;
            }
            mapp[cnt] = mapp[cnt] + 1;
        }

        int ans = 0;
        for (auto& kv : mapp) {
            int v = kv.second;
            ans += v * (v - 1) / 2;
        }

        cout << ans << endl;
    }

    return 0;
}

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();

        while (T > 0) {
            T--;

            int n = scanner.nextInt();

            List<List<Integer>> g = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                g.add(new ArrayList<>());
            }

            for (int i = 0; i < n - 1; i++) {
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                g.get(u - 1).add(v - 1);
                g.get(v - 1).add(u - 1);
            }

            Map<Integer, Integer> mapp = new HashMap<>();
            for (int u = 0; u < n; u++) {
                int cnt = g.get(u).size() - 1;
                if (u == 0) {
                    cnt += 1;
                }
                mapp.put(cnt, mapp.getOrDefault(cnt, 0) + 1);
            }

            int ans = 0;
            for (Map.Entry<Integer, Integer> entry : mapp.entrySet()) {
                int v = entry.getValue();
                ans += v * (v - 1) / 2;
            }

            System.out.println(ans);
        }
    }
}

题目内容

小美对于给定的由$n$个节点构成，根节点为$1$的有根树中，我们定义节点$u$和$v$是“相似节点”，当且仅当节点$u$的子点数量$son_u$与节点$v$的子点数量$son_u$相等。

输出“相似节点”的对数。

输入描述

每个测试文件均含多组测试数据。第一行输入一个整数$T$($1≤T≤10^4$)代表数据组数，每组测试数据描述如下：

第一行输入一个整数$n$($1≤n≤100$)代表节点数量。

此后$n-1$行，第$i$行输入两个整数$u_i$和$v_i$($1≤u_i,v_i≤n；u_i≠v_i$)表示树上第$i$条边连接节点$u_i$和$v_i$。保证树联通，没有重边。

除此之外，保证所有的$n$之和不超过$2×10^5$

输出描述

对于每一组测试数据，在一行上输出一个整数，代表图中”相似节点“的对数。

样例1

输入

1
7
1 2
1 3
3 5
3 7
2 4 
2 6

输出

9