Robocom-2022国赛-养老社区

作为智能看护的一部分，你需要评估某个养老社区是否适合开展智能看护的服务。

这个养老社区有若干幢住宅楼，每个住宅楼有一个种类，住宅楼之间由长度为 1 的道路连接，道路都是双向道路且没有构成环 —— 你可以简单地认为养老社区的路构成了一棵树。

假设我们能找到三个住宅楼，这三个住宅楼两两之间的最短距离相等，并且三个住宅楼的种类不一样，那么我们称这三个住宅楼组成的三元组为适合智能看护的，指的是为了服务这三个住宅楼，我们可能可以方便地找到适合建设服务中心的地方。一个社区的适合度指的是能够找到多少本质不同的适合智能看护的住宅楼三元组。

本质不同两个的三元组指的是：三元组内元素任意排列后，两个三元组仍然不相等。

给定这个养老社区的情况，请你求出这个社区的适合度。

输入格式:

输入第一行是一个正整数 N (1≤N≤2×103)，表示养老社区里住宅楼的数量（于是住宅楼从 1 到 N 编号）。

接下来 N−1 行，每行给出空格分隔的两个正整数 U 和 V，表示编号为 U 和 V 的住宅楼之间有一条长度为 1 的道路。

最后一行给出 N 个数，第 i 个数表示编号为 i 的住宅楼的种类为 Ti​（1≤Ti​≤N）。

保证给定的数据会将所有住宅楼连接成一棵完整的树。

输出格式:

输出一行一个正整数，表示社区的适合度。

输入样例:

11
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
1 11
1 2 3 4 5 6 7 8 9 9 10

输出样例:

14

---

 一、参考其他答主的回答

2022 RoboCom 世界机器人开发者大赛-本科组(国赛)_鲁宾孙倒拔算法的博客-CSDN博客

1.分析：

题意：给定一棵树，每个节点有一个类型，需要找出本质不同的三元组个数，即3个节点的类型各不相同，并且两两之间的最短距离相同。

题解：n次bfs找出每两节点之间的最短距离，3重循环判断每3个节点是否满足要求。

// AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
 
vector<int> G[maxn];
int n, t[maxn];
 
int vis[maxn], e[maxn][maxn];
void bfs(int x){
    queue<int> q;
    q.push(x);
    vis[x] = 1;
    while(q.size()){
        int u = q.front();
        q.pop();
        for(int to : G[u]){
            if(vis[to])continue;
            vis[to] = 1;
            e[x][to] = e[x][u]+1;
            q.push(to);
        }
    }
}
 
int main(){
    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++) cin >> t[i];
    // bfs求任意2节点距离
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) vis[j] = 0;
        bfs(i);
    }
    // 枚举3个节点
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            for(int k = j+1; k <= n; k++){
            	// 判断距离 注意由于数据量 这里的条件不能交换
                if(e[i][j]==e[j][k] && e[i][j]==e[i][k]){
                	// 判断类型
                    if(t[i]!=t[j] && t[i]!=t[k] && t[j]!=t[k]){
                        cnt++;
                    }
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

二、总结

1.如何求树中每两个点之间的距离：从每个点出发dfs，每次遍历要将Vist初始化为全0；

2.本质不同：应该不单指类型，还要包含距离，也就是一般意义上的不同