网站功能报价明细表,湖北公司网站备案严格吗,宿迁房价2022最新房价,对网络营销的理解LeetCode
边权重均等查询
2846. 边权重均等查询 - 力扣#xff08;LeetCode#xff09;
题目描述
现有一棵由 n 个节点组成的无向树#xff0c;节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges #xff0c;其中 edges[i] [ui, vi,…LeetCode
边权重均等查询
2846. 边权重均等查询 - 力扣LeetCode
题目描述
现有一棵由 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 条查询的答案。
示例 1 输入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 的路径中的所有边的权重相等的最小操作次数。示例 2 输入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 的路径中的所有边的权重相等的最小操作次数。 提示
1 n 104edges.length n - 1edges[i].length 30 ui, vi n1 wi 26生成的输入满足 edges 表示一棵有效的树1 queries.length m 2 * 104queries[i].length 20 ai, bi n
思路
代码
C
class Solution {
public:vectorint minOperationsQueries(int n, vectorvectorint edges, vectorvectorint queries) {vectorvectorpairint, int g(n);for (auto e: edges) {int x e[0], y e[1], w e[2] - 1;g[x].emplace_back(y, w);g[y].emplace_back(x, w);}int m 32 - __builtin_clz(n); // n 的二进制长度vectorvectorint pa(n, vectorint(m, -1));vectorvectorarrayint, 26 cnt(n, vectorarrayint, 26(m));vectorint depth(n);functionvoid(int, int) dfs [](int x, int fa) {pa[x][0] fa;for (auto [y, w]: g[x]) {if (y ! fa) {cnt[y][0][w] 1;depth[y] depth[x] 1;dfs(y, x);}}};dfs(0, -1);for (int i 0; i m - 1; i) {for (int x 0; x n; x) {int p pa[x][i];if (p ! -1) {int pp pa[p][i];pa[x][i 1] pp;for (int j 0; j 26; j) {cnt[x][i 1][j] cnt[x][i][j] cnt[p][i][j];}}}}vectorint ans;for (auto q: queries) {int x q[0], y q[1];int path_len depth[x] depth[y]; // 最后减去 depth[lca] * 2int cw[26]{};if (depth[x] depth[y]) {swap(x, y);}// 让 y 和 x 在同一深度for (int k depth[y] - depth[x]; k; k k - 1) {int i __builtin_ctz(k);int p pa[y][i];for (int j 0; j 26; j) {cw[j] cnt[y][i][j];}y p;}if (y ! x) {for (int i m - 1; i 0; i--) {int px pa[x][i], py pa[y][i];if (px ! py) {for (int j 0; j 26; j) {cw[j] cnt[x][i][j] cnt[y][i][j];}x px;y py; // x 和 y 同时上跳 2^i 步}}for (int j 0; j 26; j) {cw[j] cnt[x][0][j] cnt[y][0][j];}x pa[x][0];}int lca x;path_len - depth[lca] * 2;ans.push_back(path_len - *max_element(cw, cw 26));}return ans;}
};Java
class Solution {public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {Listint[][] g new ArrayList[n];Arrays.setAll(g, e - new ArrayList());for (var e : edges) {int x e[0], y e[1], w e[2] - 1;g[x].add(new int[]{y, w});g[y].add(new int[]{x, w});}int m 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度var pa new int[n][m];for (int i 0; i n; i) {Arrays.fill(pa[i], -1);}var cnt new int[n][m][26];var depth new int[n];dfs(0, -1, g, pa, cnt, depth);for (int i 0; i m - 1; i) {for (int x 0; x n; x) {int p pa[x][i];if (p ! -1) {int pp pa[p][i];pa[x][i 1] pp;for (int j 0; j 26; j) {cnt[x][i 1][j] cnt[x][i][j] cnt[p][i][j];}}}}var ans new int[queries.length];for (int qi 0; qi queries.length; qi) {int x queries[qi][0], y queries[qi][1];int pathLen depth[x] depth[y];var cw new int[26];if (depth[x] depth[y]) {int temp x;x y;y temp;}// 让 y 和 x 在同一深度for (int k depth[y] - depth[x]; k 0; k k - 1) {int i Integer.numberOfTrailingZeros(k);int p pa[y][i];for (int j 0; j 26; j) {cw[j] cnt[y][i][j];}y p;}if (y ! x) {for (int i m - 1; i 0; i--) {int px pa[x][i];int py pa[y][i];if (px ! py) {for (int j 0; j 26; j) {cw[j] cnt[x][i][j] cnt[y][i][j];}x px;y py; // x 和 y 同时上跳 2^i 步}}for (int j 0; j 26; j) {cw[j] cnt[x][0][j] cnt[y][0][j];}x pa[x][0];}int lca x;pathLen - depth[lca] * 2;int maxCw 0;for (int i 0; i 26; i) {maxCw Math.max(maxCw, cw[i]);}ans[qi] pathLen - maxCw;}return ans;}private void dfs(int x, int fa, Listint[][] g, int[][] pa, int[][][] cnt, int[] depth) {pa[x][0] fa;for (var e : g[x]) {int y e[0], w e[1];if (y ! fa) {cnt[y][0][w] 1;depth[y] depth[x] 1;dfs(y, x, g, pa, cnt, depth);}}}
}
