Минимальный путь при запросе взвешенного дерева
Дано взвешенное дерево с n вершинами. имеется q запросов, и для каждого запроса заданы целые числа (u,k). Найдите количество вершин v таких, что наименьшее ребро на пути из u в v равно k. (п, д <= 1e5)
я пробовал использовать dfs, но лучшее решение, которое я мог придумать, это O(n*q)
Мой текущий код:
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct Edge {
int to;
int weight;
};
vector<vector<Edge>> adj;
vector<int> mn;
void dfs(int u, int parent, int minWeight) {
mn[u] = minWeight;
for (auto edge : adj[u]) {
if (edge.to != parent) {
dfs(edge.to, u, min(minWeight, edge.weight));
}
}
}
int main() {
int n, q;
cin >> n >> q;
adj.resize(n + 1);
mn.resize(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
while (q--) {
int u, k;
cin >> u >> k;
fill(mn.begin(), mn.end(), INF);
dfs(u, -1, INF);
int cnt = 0;
for (int v = 1; v <= n; ++v) {
if (v != u && mn[v] == k) {
cnt++;
}
}
cout << cnt << endl;
}
return 0;
}
Было бы лучше, если бы вы могли указать требуемое время выполнения/сложность времени. Кроме того, если эта проблема связана с веб-сайтом, вам следует дать ссылку на него.
Подсказка: предположим, что имеется d различных весов ребер. Начните с удаления всех ребер, а затем добавьте их обратно в порядке убывания веса за d этапов, так чтобы на каждом этапе мы добавляли все ребра одинакового веса. Пусть compSize(x, i) — количество вершин в связном компоненте, содержащем вершину x, после i этапов, и пусть j — этап, на котором добавляются все ребра веса k. Тогда ответом на вопрос для (u, k) будет compSize(что-то) - compSize(что-то подобное). (Даже если вы зайдете так далеко, вам все равно понадобится способ эффективно вычислять и сохранять compSize()...)
Ответы 1
Эту проблему можно решить в автономном режиме, сначала прочитав все запросы, а затем отсортировав их по весу ребра в невозрастающем порядке. Мы можем использовать непересекающийся набор, чтобы поддерживать лес, сформированный только с использованием ребер с весом, превышающим определенное значение. Мы также сортируем ребра в дереве в порядке невозрастания и добавляем ребра определенного веса обратно в этом порядке. Всякий раз, когда мы добавляем ребра обратно, мы проверяем наличие запросов для этого конкретного веса. Увеличение размера компонента для любого узла после добавления этих ребер обратно — это количество вершин, у которых этот вес ребра является минимальным на пути. Обратите внимание, что запросы на веса ребер, которых нет в дереве, всегда приводят к 0.
Мы можем использовать модифицированную версию непересекающегося набора, в которой корень каждого компонента хранит отрицательный размер компонента, чтобы упростить ответ на запросы, а также реализовать объединение по размеру. Временная сложность этого решения равна O(N log N + (N + Q) log Q + (N + Q)α(N)) (где α — обратная функция Аккермана, которая здесь фактически постоянна).
Эту проблему можно решить онлайн, но код становится намного сложнее.
#include <vector>
#include <iostream>
#include <map>
#include <functional>
#include <utility>
std::vector<int> ds; // the disjoint set
int find(int u) {
return ds[u] < 0 ? u : ds[u] = find(ds[u]);
}
int main() {
int n, q;
std::cin >> n >> q;
std::vector<int> answers(q);
ds.assign(n + 1, -1);
std::map<int, std::vector<std::pair<int, int>>, std::greater<>> edgesForWeight, queriesForWeight;
for (int i = 1, u, v, w; i < n; ++i) {
std::cin >> u >> v >> w;
edgesForWeight[w].push_back({u, v});
}
for (int i = 0, u, k; i < q; ++i) {
std::cin >> u >> k;
queriesForWeight[k].push_back({i, u});
}
for (const auto& [weight, edges] : edgesForWeight) {
auto queriesIt = queriesForWeight.find(weight);
if (queriesIt != queriesForWeight.end())
for (auto [qidx, node] : queriesIt->second)
answers[qidx] = ds[find(node)];
for (auto [u, v] : edges) {
u = find(u), v = find(v);
if (ds[u] > ds[v]) std::swap(u, v);
ds[u] += ds[v];
ds[v] = u;
}
if (queriesIt != queriesForWeight.end())
for (auto [qidx, node] : queriesIt->second)
answers[qidx] -= ds[find(node)];
}
for (int ans : answers) std::cout << ans << '\n';
}
я только что добавил свой код