现有一棵由
n个节点组成的无向树，节点按从0到n - 1编号。给你一个整数n和一个长度为n - 1的二维整数数组edges，其中edges[i] = [ui, vi, wi]表示树中存在一条位于节点ui和节点vi之间、权重为wi的边。另给你一个长度为
m的二维整数数组queries，其中queries[i] = [ai, bi]。对于每条查询，请你找出使从ai到bi路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。注意：
- 查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。
- 从
ai到bi的路径是一个由 不同 节点组成的序列，从节点ai开始，到节点bi结束，且序列中相邻的两个节点在树中共享一条边。返回一个长度为
m的数组answer，其中answer[i]是第i条查询的答案。
示例一：
输入：n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]] 输出：[0,0,1,3] 解释：第 1 条查询，从节点 0 到节点 3 的路径中的所有边的权重都是 1 。因此，答案为 0 。 第 2 条查询，从节点 3 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 0 。 第 3 条查询，将边 [2,3] 的权重变更为 2 。在这次操作之后，从节点 2 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 1 。 第 4 条查询，将边 [0,1]、[1,2]、[2,3] 的权重变更为 2 。在这次操作之后，从节点 0 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 3 。 对于每条查询 queries[i] ，可以证明 answer[i] 是使从 ai 到 bi 的路径中的所有边的权重相等的最小操作次数。
示例二：
输入：n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]] 输出：[1,2,2,3] 解释：第 1 条查询，将边 [1,3] 的权重变更为 6 。在这次操作之后，从节点 4 到节点 6 的路径中的所有边的权重都是 6 。因此，答案为 1 。 第 2 条查询，将边 [0,3]、[3,1] 的权重变更为 6 。在这次操作之后，从节点 0 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 2 。 第 3 条查询，将边 [1,3]、[5,2] 的权重变更为 6 。在这次操作之后，从节点 6 到节点 5 的路径中的所有边的权重都是 6 。因此，答案为 2 。 第 4 条查询，将边 [0,7]、[0,3]、[1,3] 的权重变更为 6 。在这次操作之后，从节点 7 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 3 。 对于每条查询 queries[i] ，可以证明 answer[i] 是使从 ai 到 bi 的路径中的所有边的权重相等的最小操作次数。
题解：作者暂时也不会...，先贴的题解
代码：
const int W = 26;
class Solution {
public:
int find(vector<int> &uf, int i) {
if (uf[i] == i) {
return i;
}
uf[i] = find(uf, uf[i]);
return uf[i];
}
vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
int m = queries.size();
vector<unordered_map<int, int>> neighbors(n);
for (auto &edge : edges) {
neighbors[edge[0]][edge[1]] = edge[2];
neighbors[edge[1]][edge[0]] = edge[2];
}
vector<vector<pair<int, int>>> queryArr(n);
for (int i = 0; i < m; i++) {
queryArr[queries[i][0]].push_back({queries[i][1], i});
queryArr[queries[i][1]].push_back({queries[i][0], i});
}
vector<vector<int>> count(n, vector<int>(W + 1));
vector<int> visited(n), uf(n), lca(m);
function<void(int, int)> tarjan = [&](int node, int parent) {
if (parent != -1) {
count[node] = count[parent];
count[node][neighbors[node][parent]]++;
}
uf[node] = node;
for (auto [child, _] : neighbors[node]) {
if (child == parent) {
continue;
}
tarjan(child, node);
uf[child] = node;
}
for (auto [node1, index] : queryArr[node]) {
if (node != node1 && !visited[node1]) {
continue;
}
lca[index] = find(uf, node1);
}
visited[node] = 1;
};
tarjan(0, -1);
vector<int> res(m);
for (int i = 0; i < m; i++) {
int totalCount = 0, maxCount = 0;
for (int j = 1; j <= W; j++) {
int t = count[queries[i][0]][j] + count[queries[i][1]][j] - 2 * count[lca[i]][j];
maxCount = max(maxCount, t);
totalCount += t;
}
res[i] = totalCount - maxCount;
}
return res;
}
};
