题目描述：
现有一棵由 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\le n \le 10^4,1\le w_i \le 26, 1\le q.len \le 2\times 10^4$
题解：
首先发现 $w$ 的范围很小，可以使用前缀和维护每个节点往前每种边的个数。
由于 $n,q$ 范围比较大，不能暴力 $dfs$ 。发现可以使用 $lca$ ，使用树上前缀和配合 $lca$ 求解。
首先使用 $dfs$ 得到每个节点边种类的前缀和 $preSum[u][26]$ ，然后对每一个查询 $(u,v)$ ，先求出 $fa = lca(u,v)$ ，然后用 $preSum[u] + preSum[v] - 2 \times preSum[fa]$ 得到 $(u,v)$ 之间的边的种类及数量。然后遍历所有种类的边，哪种种类的边最多，就把别的边都变成这一种。
注意倍增法求 $lca$ 时，预先处理一个 $log2[x] = \lfloor \log_2(x) \rfloor$ 数组，然后从深度比较深的 $u$ 开始往上跳，跳到 $dep[u] = dep[v]$ ，然后一起向上跳，从 $log2[dep[u]]$ 开始递减，如果满足跳了之后父亲不同则跳，这样的话不能跳的时候说明父亲相同，直接返回 $fa[u][0]$ 就行。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e4 + 10;
const static int maxm = 1e1 + 10;
const int INF = 0x3f3f3f3f;
struct Node
{
int v, w;
Node(int _v, int _w) : v(_v), w(_w) {}
};
int preSum[maxn][27] = {};
int fa[maxn][14] = {};
int dep[maxn] = {};
int log2[maxn] = {};
vector<Node> g[maxn];
int n, m;
void dfs(int u, int father)
{
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i].v, w = g[u][i].w;
if (v == father)
continue;
for (int i = 1; i <= 26; ++i)
{
preSum[v][i] = preSum[u][i];
}
fa[v][0] = u;
preSum[v][w] += 1;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
void init()
{
for (int i = 1; i < 14; ++i)
{
for (int u = 0; u < n; ++u)
{
if (fa[u][i - 1] != -1)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
else
fa[u][i] = -1;
}
}
log2[0] = log2[1] = 0;
for (int i = 2; i <= n; ++i)
{
log2[i] = log2[i >> 1] + 1;
}
}
int lca(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
int tmp = dep[u] - dep[v];
while (tmp != 0)
{
u = fa[u][log2[tmp]];
tmp -= 1 << log2[tmp];
}
if (u == v)
return u;
for (int i = log2[dep[u]]; i >= 0; --i)
{
if (fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
vector<int> minOperationsQueries(int _n, vector<vector<int>> &edges, vector<vector<int>> &queries)
{
n = _n;
m = edges.size();
int q = queries.size();
for (auto &edge : edges)
{
g[edge[0]].emplace_back(edge[1], edge[2]);
g[edge[1]].emplace_back(edge[0], edge[2]);
}
dfs(0, -1);
init();
vector<int> ret;
for (auto &query : queries)
{
int u = query[0], v = query[1];
if(u == v)
{
ret.push_back(0);
continue;
}
int fa = lca(u, v);
int maxx = 0, sum = 0;
for (int i = 1; i <= 26; ++i)
{
int cnt = preSum[u][i] + preSum[v][i] - 2 * preSum[fa][i];
maxx = max(maxx, cnt);
sum += cnt;
}
ret.push_back(sum - maxx);
}
return ret;
}
};
|