题解分享
题解分享简介
狡兔 k 窟（编程题） - 题解
真坑啊, 原来 $c_i$ 可以 大于 $n$, 之前一直拿 n 开数组, 我说怎么过不去qwq
```cpp
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
using ll = long long;
struct Ac {
void run() {
constexpr int N = 1e5;
int n, m;
cin >> n >> m;
vector<int> zu(N);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
--x;
zu[i] = x;
}
vector<vector<int>> g(N);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
u = zu[u];
v = zu[v];
if (u == v)
continue;
g[u].push_back(v);
g[v].push_back(u);
}
while (m--) {
int s, t;
cin >> s >> t;
--s, --t;
int go = zu[s], to = zu[t];
if (go == to) {
cout << "0\n";
continue;
}
vector<int> vis(N);
// cnt, now
queue<tuple<int, int>> q;
vis[go] = 1;
q.push(tuple<int, int>{0, go});
while (q.size()) {
int cnt, now;
tie(cnt, now) = q.front();
q.pop();
++cnt;
for (int it : g[now]) {
if (it == to) {
cout << cnt << '\n';
goto End;
}
if (vis[it])
continue;
vis[it] = 1;
q.push(tuple<int, int>{cnt, it});
}
}
End:
;
}
}
};
int main() {
Ac ak;
ak.run();
return 0;
}
```
查看全文
0
0
0
3
