折磨

猫猫的社交网络中有 $N$ 位用户，他们编号为 $1\sim N$，其中猫猫的编号为 $A$。

每名用户的心中都会有一个心动价位 $a_i$，当它看到的瓜条金额 $\ge$ 心动价位，该用户就会心动并转发该瓜条，同时它的心动价位也会更新为瓜条金额。

现在有 $M$ 位用户在同一时刻发出了瓜条，瓜条金额为发出者的初始心动价位，不会再变。每个瓜条一旦发出就会出现在该用户空间里，该用户的所有好友立即可见；好友若心动会转发，转发的瓜条会出现在该好友的空间里，对该好友的所有好友可见，如此层层扩散……

由于这只笨猫没有底线（其心动价位为 $0$），为了避免自己转发，在他看到任何瓜条前，猫猫决定立刻屏蔽自己的一些好友，猫猫不会查看被自己屏蔽的好友的空间。

那么猫猫至少需要屏蔽多少个好友呢？可以证明看到瓜条的顺序并不会影响最终结果。

输入格式

第一行 $4$ 个正整数 $N,E,M,A$，代表着总用户数、好友关系数、发送瓜条的用户数、猫猫的编号。

接下来 $1$ 行共有 $N$ 个非负整数，代表着每名用户初始的心动价位 $a_i$。

接下来 $E$ 行，每行 $2$ 个正整数 $u,v$，代表着用户 $u$ 和用户 $v$ 是好友关系。

接下来 $1$ 行共有 $M$ 个正整数，代表着发送瓜条用户的编号，数据保证猫猫自己不会发送瓜条。

输出格式

一个整数，代表着最少需要屏蔽的好友数目。

样例

输入样例 1

6 8 2 3
0 0 0 0 1 0
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 6

输出样例 1

2

输入样例 2

6 8 1 3
0 0 0 0 0 0
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4

输出样例 2

1

样例 1 的解释

在本组样例中一共涉及到 $6$ 名用户，有 $8$ 对好友关系，猫猫的节点编号为 $3$，关系网络中有 $2$ 名瓜条发送者：用户 $4$ 和用户 $6$。

其中猫猫的好友为用户 $1$、用户 $4$、用户 $5$。由于用户 $6$ 的瓜条金额 $0$ 达到了用户 $1$ 的心动价位 $0$，因此用户 $1$ 将会转发瓜条，而用户 $5$ 的心动价位 $1$ 高于用户 $6$ 的瓜条金额 $0$，因此用户 $5$ 不会转发瓜条。

而用户 $4$ 既是猫猫的好友，又是瓜条的发送者，它的空间内也有瓜条。

因此，如果猫猫不想看到瓜条，最终至少需要屏蔽 $2$ 个好友：用户 $1$ 和用户 $4$。

因此最终答案输出 $2$。

数据范围与约束

本题共有 $30$ 个测试点，对于第 $1\sim20$ 个测试点，每个测试点通过后可以得到 $3$ 分；对于第 $21\sim30$ 个测试点，每个测试点通过后可以得到 $4$ 分。

对于 $100\%$ 的数据满足：$1\le A,u,v \le N$，$1\le M < N$，$0 \le a_i \le 10^9$，$E \ge 1$。

测试点编号	$E$	$N$	特殊性质
$1\sim2$	$\le10$	$\le10$	$A,E$
$3$	^	^	$B,E$
$4\sim5$	^	^	$C,E$
$6$	^	^	$D,E$
$7\sim8$	^	^	$E$
$9\sim10$	^	^	无
$11\sim12$	$\le800$	$\le800$	$A,E$
$13$	^	^	$B,E$
$14\sim15$	^	^	$C,E$
$16$	^	^	$D,E$
$17\sim18$	^	^	$E$
$19\sim20$	^	^	无
$21\sim22$	$\le 2 \times 10^5$	$\le 2 \times 10^5$	$A,E$
$23$	^	^	$B,E$
$24\sim25$	^	^	$C,E$
$26$	^	^	$D,E$
$27\sim28$	^	^	$E$
$29\sim30$	^	^	无

特殊性质 $A$：心动价位最高的用户一定是瓜条发送者，且在没有屏蔽任何用户的条件下，该用户的瓜条最终会被猫猫的每一位好友看见。

特殊性质 $B$：社交网络是一棵树。

特殊性质 $C$：社交网络是菊花图。

特殊性质 $D$：社交网络是一条链。

特殊性质 $E$：社交网络是连通图。

这道题的核心是分析瓜条信息的传播机制，以及猫猫为了不看到任何瓜条，需要切断哪些连向其好友的边。

解题思路分析

建模与信息传播规则

网络是一个无向图，包含 $N$ 个节点和 $E$ 条边。猫猫位于节点 $A$。

对于任何一个瓜条，它的本质是一个带有权值（金额）$W$ 的信息，在图上传播：

当金额为 $W$ 的瓜条传到节点 $u$ 时：

• 如果 $W \ge a_u$，节点 $u$ 会心动并转发（同时其心动价位更新为 $W$），该瓜条会继续传给 $u$ 的所有邻居。
• 如果 $W < a_u$，节点 $u$ 不转发，传播在该节点终止。

关键观察：

如果节点 $u$ 转发了某个瓜条，其心动价位会提高（更新）为 $W$。后续如果有金额更高（$\ge W$）的瓜条到来，由于金额依然大于等于当前已抬高的心动价位，节点 $u$ 依然会继续转发。而在本题的求解逻辑中，只要猫猫的好友自身是发瓜者，或者至少转发过一次瓜条，猫猫就必须将其屏蔽。

判断猫猫的好友是否会看到/发出瓜条

题目只允许猫猫屏蔽自己的好友（即删除节点 $A$ 与其邻居 $u \in \text{adj}(A)$ 之间的边）。

猫猫不能改变其他节点之间的传播逻辑，因此：

• 如果猫猫的某个好友 $u$ 最终拥有/转发了任何一个瓜条，那么猫猫如果不屏蔽 $u$，就一定会从 $u$ 这里看到瓜条。
• 只要确定哪些好友 $u \in \text{adj}(A)$ 最终会触发瓜条转发（或本身就是初始发瓜者），猫猫就必须屏蔽这些好友。

因此，最少屏蔽的好友数 = 猫猫的所有好友中，最终能够拥有/转发瓜条的节点个数。

传播过程求解算法 (BFS / Dijkstra)

题目保证删去猫猫与好友的边不影响传播本身（因为猫猫自己不会发瓜，且猫猫心动价为 $0$，屏蔽发生在传播之前，猫猫只作为一个被动接收端）。

我们可以直接在去掉了猫猫节点 $A$ 的图上（或者原图上不经过 $A$）运行多源最短路/松弛算法：

1. 定义状态：

   $val[u]$ 表示到达节点 $u$ 的瓜条的最大金额（初始全为 $-1$）。

   如果初始节点 $v$ 是发瓜者，则其初始拥有金额为 $a_v$ 的瓜条，即 $val[v] = a_v$。

2. 传播机制：

   用类似于 Dijkstra 或 SPFA/BFS 的优先队列（按瓜条金额从大到小排序）：

   • 优先处理当前金额较大的瓜条。当节点 $u$ 拥有金额为 $W$ 的瓜条且 $W \ge a_u$ 时，它会将 $W$ 传播给所有邻居 $v$。
   • 如果 $W > val[v]$，更新 $val[v] = W$，并将 $(W, v)$ 加入队列。

3. 统计答案：

   在传播结束后，遍历猫猫的所有好友 $u \in \text{adj}(A)$：

   • 如果 $u$ 是初始发瓜者，或者 $val[u] \ge a_u$（即 $u$ 收到过金额 $\ge a_u$ 的瓜条），则猫猫必须屏蔽 $u$。
   • 统计满足条件的好友数量，即为答案。

参考代码

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

using namespace std;

const int MAXN = 200005;

struct Node {
    int u;
    int w;
    bool operator<(const Node& other) const {
        return w < other.w; // 大顶堆，优先传播金额大的瓜条
    }
};

int N, E, M, A;
int a[MAXN];
vector<int> adj[MAXN];
int max_w[MAXN]; // 记录节点到达的最大瓜条金额
bool is_sender[MAXN];

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

    cin >> N >> E >> M >> A;
    for (int i = 1; i <= N; ++i) {
        cin >> a[i];
        max_w[i] = -1;
    }

    for (int i = 0; i < E; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    priority_queue<Node> pq;

    for (int i = 0; i < M; ++i) {
        int sender;
        cin >> sender;
        is_sender[sender] = true;
        max_w[sender] = a[sender];
        pq.push({sender, a[sender]});
    }

    // 传播过程（传播时跳过猫猫节点 A）
    while (!pq.empty()) {
        auto [u, w] = pq.top();
        pq.pop();

        if (w < max_w[u]) continue;

        for (int v : adj[u]) {
            if (v == A) continue; // 猫猫屏蔽了自己，不参与传播过程

            // 如果瓜条金额大于等于邻居的心动价，且比邻居收到的已有最大金额更大
            if (w >= a[v] && w > max_w[v]) {
                max_w[v] = w;
                pq.push({v, w});
            }
        }
    }

    // 统计猫猫需要屏蔽的好友数量
    int ans = 0;
    for (int u : adj[A]) {
        // 如果好友自身发了瓜，或者收到了能够触发转发的瓜
        if (is_sender[u] || max_w[u] >= a[u]) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}