阿里秋招笔试题（附答案）

1、树上最短链

【题目描述】

在一个地区有n个城市以及n-1条无向边，每条边的时间边权都是1，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。

现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。

但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。

输入描述：

第一行一个正整数n，含义如题面所述。

第二行n个正整数Ai，代表每个城市的等级。

接下来n-1行每行两个正整数u，v代表一条无向边。

保证给出的图是一棵树。

1≤n≤5000

1≤u，v≤n

1≤Ai≤109

输出描述：

仅一行一个整数代表答案，如果无法满足要求，输出 -1 。

输入样例：

3

1 2 1

1 2

2 3

输出样例：

2

【解题思路】

数据量比较小，直接dfs即可。

【参考代码】

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, a[5005], root, ans = 1e9;
vector<int> e[5005];
void dfs(int r, int f, int deep) {
    if (r != root && a[r] == a[root])
        ans = min(ans, deep);
    for (int i = 0; i < e[r].size(); i++)
        if (e[r][i] != f)
            dfs(e[r][i], r, deep + 1);
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int i, j, x, y;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    for (i = 1; i < n; i++) {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (i = 1; i <= n; i++) {
        root = i;
        dfs(i, 0, 0);
    }
    cout << (ans == 1e9 ? -1 : ans);
    return 0;
}

资料全部内容请看《2024校招笔试真题秘籍》

不收费，3人组团即可免费领取！已经发出1000份了，涵盖各大公司历年笔试真题+答案，助你事半功倍！

资料包含：

• 30+大厂笔试真题
• 腾讯、阿里、华为、字节、小米、美团、拼多多......
• 100+道技术真题解析&答案

全网独家资料

手机端点击领取：https://www.nowcoder.com/link/campus_xzbs5

电脑端请扫描领取：

资料部分内容展示↓