从给定 DAG 中存在的每个节点开始可到达的节点总和，并限制每个节点的子节点数量

Question

这是 XXX 波兰信息学奥林匹克竞赛第二阶段的题目“Wspinaczka”。 链接到波兰语的原始问题陈述。

让我们将上面的故事压缩成算法问题陈述：

给定有向无环图（DAG）

g

，对于该图中的每个顶点

p

，如果我们从

g

开始遍历，则计算所有可达节点的总和。节点的值以数组形式给出，其中第 i 个值对应于第 i 个顶点。

众所周知，当我们位于顶点p

时，只有当

i

时，才存在从节点

i

到节点

j

的有向边。此外，我们得到

j > i

，

k

并且以下条件必须成立：

1 <= k <= 8

有

j - i <= k 节点、

n

和

1 <= n <= 100 000

边

m

我就是这样开始的：

1 <= m <= 800 000

所以我执行拓扑排序（首先处理 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    // values of nodes
    vector<int> beauty(n);
    for (int i = 0; i < n; ++i)
        cin >> beauty[i];

    vector<vector<int>> adj_list(n);
    vector<vector<int>> reversed_adj_list(n);
    vector<int> outgoing_edges(n);
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;

        --a;
        --b;

        adj_list[a].push_back(b);
        reversed_adj_list[b].push_back(a);
        ++outgoing_edges[a];
    }

    queue<int> q;
    for (int i = 0; i < n; ++i)
    {
        if (outgoing_edges[i] == 0)
        {
            q.push(i);
        }
    }

    vector<long long> dp(n);
    while (!q.empty())
    {
        int node = q.front();
        q.pop();

        dp[node] = beauty[node];
        for (const int child : adj_list[node])
        {
            dp[node] += dp[child];
        }

        for (const int parent : reversed_adj_list[node])
        {
            --outgoing_edges[parent];

            if (outgoing_edges[parent] == 0)
            {
                q.push(parent);
            }
        }
    }

    for (int i = 0; i < n; ++i)
        cout << dp[i] << '\n';
}

节点，然后是

n

，然后是

n-1

节点，依此类推，因为我们知道，只有当

n-2

时，节点

i

和

j

之间才能存在边） ).在进行这种拓扑排序时，我像这样计算

j > i

：

dp[i]

。问题是这多算了。为什么？见下图（红色数字为数值）：

对于节点 1，我们正在对所有子图及其子图的值求和，但是这两个子图都已经计算了节点 4。因此，当我从节点

dp[i] = value[i] + sum_of_values_of_all_childs

开始时，计算出的答案是

13

，而不是结果

1

因为我对

14

节点数了两次。我不知道如何避免这种情况，而且我没有利用

4

的小值。我知道存在使用

k

的解决方案，其中掩码高达

dp[node][mask]

，但我无法找到它。该解决方案的时间复杂度为

2^K

（m 因为读取输入）。

Answer 1

O(n * 2^K + m)

：可以从顶点的掩码子集 {i+1 精确到达的顶点值的总和...i+k}。对 i 的可达掩码求和可以给出问题的答案。

我们只需要在添加顶点 i 后重新计算 DP，即计算 {i...i+k-1} 掩码的

dp[mask]

。请注意，每个顶点在 DP 中只计算一次，因此我们只需要为每个

dp_new[mask_new]

计算唯一给定的新掩码，并将权重总和添加到更新的 DP 数组中。对于每个

dp[mask]

，我们知道

mask

的前k-1位是

mask

的后k-1位，所以这只是一个移位；所有 k 位告诉我们是否正在处理从 i 可达的顶点（它们确定新掩码的第一位），并且第 k 位不用于其他任何操作。最后我们将顶点 i 的权重添加到

mask_new

。所有带有掩码的计算都使用 O(1) 位运算，这具有所需的时间复杂度。