[WC2014] 紫荆花之恋 - 解题思路与代码实现

[WC2014] 紫荆花之恋 - 解题思路与代码实现

题目描述

强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点，每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 'i' 都有一个感受能力值 'r_i'，小精灵 'i,j' 成为朋友当且仅当在树上 'i' 和 'j' 的距离 'dist(i,j)' ≤ 'r_i+r_j'，其中 'dist(i,j)' 表示在这个树上从 'i' 到 'j' 的唯一路径上所有边的边权和。

强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。

我们假定这个树一开始为空，节点按照加入的顺序从 1 开始编号。由于强强非常好奇，你必须在他每次出现新结点后马上给出总共的朋友对数，不能拖延哦。

输入格式

第一行包含一个整数，表示测试点编号。

第二行包含一个正整数 'n'，表示总共要加入的节点数。

我们令加入节点前的总共朋友对数是 'last_ans'，在一开始时它的值为 0。

接下来 'n' 行中第 'i' 行有三个非负整数 'a_i,c_i,r_i'，表示结点 'i' 的父节点的编号为 'ai ⊕ (last_ans mod 10^9)'（其中 '⊕' 表示异或，数据保证这样操作后得到的结果介于 1 到 'i−1' 之间），与父结点之间的边权为 'c_i'，节点 'i' 上小精灵的感受能力值为 'r_i'。

注意 'a_1=c_1=0'，表示 1 号节点是根结点，对于 'i>1'，父节点的编号至少为 1。

输出格式

包含 'n' 行，每行输出 1 个整数，表示加入第 'i' 个点之后，树上有几对 friends。

样例 #1

样例输入 #1

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

样例输出 #1

0
1
2
4
7

提示

所有数据均满足 '1 ≤ c_i ≤ 10^4'，'a_i ≤ 2×10^9'，'r_i ≤ 10^9'。

| 测试点编号 | 约定 | | :----------------: | :------------------------------------------------------------: | | $1,2$ | $n ≤ 100$ | | $3,4$ | $n ≤ 1000$ | | $5,6,7,8$ | $n ≤ 10^5$，节点 1 最多有两个子节点，其他节点最多有一个子节点 | | $9,10$ | $n ≤ 10^5$，$r_i ≤ 10$ | | $11,12$ | $n ≤ 10^5$，树是随机生成的 | | $13,14,15$ | $n ≤ 7×10^4$ | | $16,17,18,19,20$ | $n ≤ 10^5$ |

思路解析

这是一道带权树的问题，需要动态维护每个节点上的小精灵的感受能力值，并根据节点之间的距离判断是否为朋友。

我们可以使用一个数组 friends 来记录每个节点上的小精灵的感受能力值，初始时都为0。每次加入一个新节点时，更新 friends 数组，并计算新加入节点和已有节点之间的距离，判断是否为朋友。

为了方便计算节点之间的距离，我们可以使用一个二维数组 dist 来存储任意两个节点之间的距离。初始时，dist[i][j] 表示节点i到节点j之间的距离，即节点i到根节点经过的边权和。

对于每个新加入的节点i，我们可以通过遍历已有节点j，计算 dist[i][j] 的值。具体计算方法如下：

• 如果节点i的父节点编号为a，那么 dist[i][j] = dist[a][j] + c[i]，其中c[i]是节点i和其父节点之间的边权。
• 如果节点i的父节点编号为0，那么 dist[i][j] = c[i]，即节点i到节点j的距离等于节点i到根节点经过的边权和。

计算完 dist[i][j] 后，我们可以遍历已有节点j，计算节点i和节点j之间的距离，判断是否为朋友。如果 dist[i][j] ≤ r[i] + friends[j]，那么节点i和节点j是朋友，我们可以更新 friends[i] 和 friends[j]。

最后，我们输出每次加入节点后的朋友对数。

代码实现

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100000;

int friends[MAXN + 1];
int dist[MAXN + 1][MAXN + 1];

int main() {
    int test_case;
    cin >> test_case;

    while (test_case--) {
        int n;
        cin >> n;

        vector<int> a(n + 1);
        vector<int> c(n + 1);
        vector<int> r(n + 1);

        for (int i = 1; i <= n; ++i) {
            cin >> a[i] >> c[i] >> r[i];

            int p = a[i] ^ (friends[0] % 1000000000);
            dist[i][0] = c[i];

            for (int j = 1; j <= n; ++j) {
                dist[i][j] = dist[p][j] + c[i];
            }
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                if (dist[i][j] <= r[i] + friends[j]) {
                    friends[i]++;
                    friends[j]++;
                }
            }
        }

        for (int i = 1; i <= n; ++i) {
            cout << friends[i] << endl;
        }
    }

    return 0;
}

复杂度分析

由于需要遍历已有节点计算节点之间的距离，并更新朋友关系，所以时间复杂度为O(n^2)。其中，n是节点数。

空间复杂度为O(n^2)，需要使用二维数组来存储任意两个节点之间的距离。