2846. 邊權(quán)重均等查詢

輸入：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 條查詢，從節(jié)點 0 到節(jié)點 3 的路徑中的所有邊的權(quán)重都是 1 。因此，答案為 0 。
第 2 條查詢，從節(jié)點 3 到節(jié)點 6 的路徑中的所有邊的權(quán)重都是 2 。因此，答案為 0 。
第 3 條查詢，將邊 [2,3] 的權(quán)重變更為 2 。在這次操作之后，從節(jié)點 2 到節(jié)點 6 的路徑中的所有邊的權(quán)重都是 2 。因此，答案為 1 。
第 4 條查詢，將邊 [0,1]、[1,2]、[2,3] 的權(quán)重變更為 2 。在這次操作之后，從節(jié)點 0 到節(jié)點 6 的路徑中的所有邊的權(quán)重都是 2 。因此，答案為 3 。
對于每條查詢 queries[i] ，可以證明 answer[i] 是使從 ai 到 bi 的路徑中的所有邊的權(quán)重相等的最小操作次數(shù)。

分析

如果暴力寫的話， 那么對于每一個查詢，我們要dfs一遍，每一遍存一下路徑上的邊權(quán)得數(shù)量，最后用總的數(shù)量減去最多的變得數(shù)量就是答案，這是一個小貪心的思路，那么考慮一下數(shù)據(jù)范圍，如果暴力寫的話，時間復(fù)雜度是$O(n^2)$，肯定會超時的，但是也吧暴力寫法的代碼貼出來。

723 / 733 個通過的測試用例

暴力 dfs （會超時）

class Solution {
public:vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {int m = queries.size();vector<int> e(n << 1), ne(n << 1), h(n, -1), w(n << 1), ans(m); // 鏈式向前星int cnt[27], idx = 0;// addfunction<void(int, int, int)> add = [&](int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;e[idx] = a, ne[idx] = h[b], w[idx] = c, h[b] = idx ++;}; // add// dfsfunction<bool(int, int, int)> dfs = [&](int u, int b, int fa) {if (u == b) {return true;}for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (j == fa) continue;if (dfs(j, b, u)) {++ cnt[w[i]];return true;}}return false;}; // dfsfor (int i = 0; i < n - 1; i ++ ) {int a = edges[i][0], b = edges[i][1], w = edges[i][2];add(a, b, w);}for (int i = 0; i < m; i ++) {memset(cnt, 0, sizeof cnt); // 每次清空數(shù)組int a = queries[i][0], b = queries[i][1];dfs(a, b, -1);int res = 0, sum = 0;for (int i = 1; i <= 26; i ++) {sum += cnt[i];res = max(res, cnt[i]);}ans[i] = sum - res;}return ans;}
};

時間復(fù)雜度：$O(n?m?W)$ (本題 W = 26)

分析

我們可以用最近公共祖先的思想，選定一個根節(jié)點，假設(shè)是0，那么定義一個cnt[i][w]表示節(jié)點i到根節(jié)點的路徑中邊權(quán)為w(1 <= w <= 26)的邊的數(shù)量，那么i到j之間邊權(quán)為w的邊數(shù)是$t_a=cnt[i][w]+cnt[j][w]?2?cnt[lca(i,j)][w]$，lca(i, j)表示節(jié)點i和節(jié)點j的最近公共祖先, 那么要替換的邊數(shù)就是
$$\sum _{i=1}^{26}{t}_i?\underset{1<=i<=26}{\max }{t}_i$$
使用離線算法tarjan算法模板

tarjan + 并查集

class Solution {
public:using PII = pair<int, int>;vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {int m = queries.size();vector<unordered_map<int, int>> g(n);for (auto& e : edges) {g[e[0]][e[1]] = e[2];g[e[1]][e[0]] = e[2];}vector<vector<PII>> q(n);   for (int i = 0; i < m; i ++ ){q[queries[i][0]].push_back({queries[i][1], i});q[queries[i][1]].push_back({queries[i][0], i});}vector<int> lca(m), vis(n), p(n);iota(p.begin(), p.end(), 0);vector<vector<int>> cnt(n, vector<int>(27));function<int(int)> find = [&](int x) {if (x != p[x]) p[x] = find(p[x]);return p[x];};function<void(int, int)> tarjan = [&](int u, int fa) {if (fa != -1) {cnt[u] = cnt[fa];++ cnt[u][g[u][fa]];}p[u] = u;for (auto& e : g[u]) {if (e.first == fa) continue;tarjan(e.first, u);p[e.first] = u;}for (auto& e : q[u]) {if (u != e.first && !vis[e.first]) continue;lca[e.second] = find(e.first);}vis[u] = 1;};tarjan(0, -1);vector<int> res(m);for (int i = 0; i < m; i ++ ){int sum = 0, mx = 0;for (int j = 1; j <= 26;j ++) {int t = cnt[queries[i][0]][j] + cnt[queries[i][1]][j] - 2 * cnt[lca[i]][j];mx = max(mx, t);sum += t;}res[i] = sum - mx;}return res;}
};

時間復(fù)雜度：$O((m+n)\times W+m\times logn)$ (本題 W = 26)

在線lca算法

const int N = 10010;
class Solution {
public:int e[N << 1], ne[N << 1], w[N << 1], h[N],  idx;int fa[N][15], depth[N];int cnt[N][27], cntn[27];int q[N];void bfs() {int hh = 0, tt = 0;q[0] = 1;memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;while (hh <= tt) {int t = q[hh ++ ];for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q[ ++ tt] = j;fa[j][0] = t;for (int k = 1; k <= 14; k ++ )fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}}// dfs版本void dfs_dep(int u, int father) {depth[u] = depth[father] + 1;fa[u][0] = father;for (int i = 1; i <= 14; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];for (int i = h[u]; ~i; i = ne[i]) {if (e[i] != father) {dfs_dep(e[i], u);}}}void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;}void dfs(int u, int fa) {memcpy(cnt[u], cntn, sizeof cntn);for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (fa == j) continue;cntn[w[i]] ++;dfs(j, u);cntn[w[i]] -- ;}}int lca(int a, int b){if (depth[a] < depth[b]) swap(a, b);for (int k = 14; k >= 0; k -- )if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];if (a == b) return a;for (int k = 14; k >= 0; k -- ) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];}vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {memset(h, -1,sizeof h);for (int i = 0; i < edges.size(); i ++ ) {int a = edges[i][0], b = edges[i][1], c = edges[i][2];a ++, b ++ ;add(a, b, c), add(b, a, c);}bfs();// dfs_dep(1, 0); // dfs_dep版本dfs(1, -1);vector<int> ans(queries.size());for (int i = 0; i < queries.size(); i ++ ) {int a = queries[i][0], b = queries[i][1];a ++, b ++ ;int p = lca(a, b);vector<int> s(27);for (int j = 1; j <= 26; j ++ )s[j] += cnt[a][j] + cnt[b][j] - cnt[p][j] * 2;int sum = 0, maxv = 0;for (int j = 1; j <= 26; j ++ ) {maxv = max(maxv, s[j]);sum += s[j];}ans[i] = sum - maxv;}return ans;}
};

時間復(fù)雜度：$O(mlogn)$