5.4 统治世界

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

大陆上有\(N\)个国家，由\(N-1\)条道路连接，保证两两连通。我们将国家分布看成一个树形结构，以标号为 1 的国家为根节点。每个国家都有一个综合实力\(A_i\)，每条道路上有一个长度\(W_i\)。现在，如果国家\(V\)可以攻打国家\(U\)，当且仅当在树形结构图中，\(U\)在\(V\)的子树中，且\(dist(v,u)\leq A_u\ (V\neq U)\)，\(dist(v,u)\)表示\(u\)到\(v\)的最短路。现在想请你帮忙计算每个国家可以攻打的国家数目。

数据输入

第一行包含一个整数\(N\ (1\leq N\leq 20000)\)，表示国家的个数。第二行包含\(N\)个正整数\(A_1,A_2,\cdots , A_n\ (1\leq A_i\leq 10^9)\)，表示国家的综合实力。接下去输入\(N-1\)行，第\(i\)行包括两个整数\(P_i\)和\(W_i\ (1\leq P_i\leq N,1\leq W_i\leq 10^9)\)，表示标号为\(P_i\)的国家是标号为\(i+1\)的国家的父节点，且两个国家之间的道路长度为\(W_i\)。

数据输出

输出为\(N\)个整数，表示每个国家可以攻打的国家个数。

输入示例 输出示例
5 6
4 1 2 6
1 2
1 2
2 4
2 5		 1 1 0 0 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
#include <stdio.h>
using namespace std;
#define maxn 20005

class Node{
public:
    int power, weight, parent, scale;
    Node() :power(0), weight(0), parent(0), scale(0){}
};

class Tree{
public:
    int n;
    Node node[maxn];
    void in(){
        scanf("%d", &n);
        int i;
        for (i = 1; i <= n; ++i)
            scanf("%d", &node[i].power);
        for (i = 2; i <= n; ++i){
            scanf("%d%d", &node[i].parent, &node[i].weight);
        }
    }
    void solve(){
        for (int i = 2; i <= n; ++i){
            int son = i;
            int power = node[son].power;
            while (son > 1 && power >= node[son].weight){
                ++node[node[son].parent].scale;
                power -= node[son].weight;
                son = node[son].parent;
            }
        }
    }
    void out(){
        printf("%d", node[1].scale);
        for (int i = 2; i <= n; ++i)
            printf(" %d", node[i].scale);
        printf("\n");
    }
}tree;

int main(){
    tree.in();
    tree.solve();
    tree.out();
    return 0;
}

设计思路与复杂度分析

题目源于实际：地球上有若干国家，国家之间的相互制约表现为“强国” 控制弱国。控制国需要保证对其所有被控国的绝对控制力。即：若某一个被控国的势力范围达到其大本营，则控制国将要攻打该被控国，削弱其势力。而我们的任务是帮助每一个控制国求解其需要攻打的被控国数量。所以不难理解为何是：子节点的实力大于其到父节点的路径长度，则父节点攻打子节点。所以美国虽然控制整个地球，他也没有天天打仗嘛！因为他只是需要一个平衡，然后坐收渔利！

输入的数据是每一个节点的父节点、到父节点的路径长度以及自身的势力。根据输入数据，将任务转化为对于每一个节点计算其所有父节点是否可以攻击他，并将结果存储在该父节点处。所以对于每一个节点，回溯其势力范围内的祖先节点并将其攻击数加一。

平均时间复杂度\(O(n\times logn)\)，最坏时间复杂度\(O(n^2)\)。

0%