310191: CF1795G. Removal Sequences

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Removal Sequences

题意翻译

你有一张简单无向图,这张图上有 $n$ 个点 $m$ 条边,顶点编号为 $1 \sim n$,第 $i$ 个顶点的权值是 $a_i$。 你将删除一些顶点,特别的,定义删除顶点 $i$ 是合法的仅当 $i$ 的度数为 $a_i$,删除某个顶点后,与这个顶点相连的边也会被删除。 我们称一个移除序列 $p$ 是有效的当且仅当 $p_1,p_2,...p_n$ 是一个 $1 \sim n$ 的排列,且若依次删除 $p_1,p_2,...p_n$,每次删除都是合法的。 若存在两个合法的移除序列分别满足 $x$ 在 $y$ 前删除,$y$ 在 $x$ 前删除,且 $x<y$,则点对 $(x,y)$ 是美好的。 请统计所有“美好”的点对数量。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

题目描述

You are given a simple undirected graph, consisting of $ n $ vertices and $ m $ edges. The vertices are numbered from $ 1 $ to $ n $ . The $ i $ -th vertex has a value $ a_i $ written on it. You will be removing vertices from that graph. You are allowed to remove vertex $ i $ only if its degree is equal to $ a_i $ . When a vertex is removed, all edges incident to it are also removed, thus, decreasing the degree of adjacent non-removed vertices. A valid sequence of removals is a permutation $ p_1, p_2, \dots, p_n $ $ (1 \le p_i \le n) $ such that the $ i $ -th vertex to be removed is $ p_i $ , and every removal is allowed. A pair $ (x, y) $ of vertices is nice if there exist two valid sequences of removals such that $ x $ is removed before $ y $ in one of them and $ y $ is removed before $ x $ in the other one. Count the number of nice pairs $ (x, y) $ such that $ x < y $ .

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains two integers $ n $ and $ m $ ( $ 1 \le n \le 10^5 $ ; $ 0 \le m \le \min(10^5, \frac{n \cdot (n - 1)}{2}) $ ) — the number of vertices and the number of edges of the graph. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le n - 1 $ ) — the degree requirements for each removal. Each of the next $ m $ lines contains two integers $ v $ and $ u $ ( $ 1 \le v, u \le n $ ; $ v \neq u $ ) — the description of an edge. The graph doesn't contain any self-loops or multiple edges. The sum of $ n $ over all testcases doesn't exceed $ 10^5 $ . The sum of $ m $ over all testcases doesn't exceed $ 10^5 $ . Additional constraint on the input: there always exists at least one valid sequence of removals.

输出格式


For each testcase, print a single integer — the number of nice pairs of vertices.

输入输出样例

输入样例 #1

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

输出样例 #1

1
0
4
0

Input

题意翻译

你有一张简单无向图,这张图上有 $n$ 个点 $m$ 条边,顶点编号为 $1 \sim n$,第 $i$ 个顶点的权值是 $a_i$。 你将删除一些顶点,特别的,定义删除顶点 $i$ 是合法的仅当 $i$ 的度数为 $a_i$,删除某个顶点后,与这个顶点相连的边也会被删除。 我们称一个移除序列 $p$ 是有效的当且仅当 $p_1,p_2,...p_n$ 是一个 $1 \sim n$ 的排列,且若依次删除 $p_1,p_2,...p_n$,每次删除都是合法的。 若存在两个合法的移除序列分别满足 $x$ 在 $y$ 前删除,$y$ 在 $x$ 前删除,且 $x<y$,则点对 $(x,y)$ 是美好的。 请统计所有“美好”的点对数量。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

Output

题目大意:
你有一个简单无向图,包含n个顶点和m条边。顶点编号为1到n,第i个顶点有权值a_i。你可以删除一些顶点,但只有当顶点i的度数等于a_i时,删除才是合法的。删除一个顶点后,与该顶点相连的所有边也会被删除。一个有效的移除序列p是1到n的一个排列,使得按照p的顺序删除每个顶点都是合法的。如果存在两个有效的移除序列,其中一个序列中x在y之前被删除,另一个序列中y在x之前被删除,且x
输入输出数据格式:
输入格式:
- 第一行包含一个整数t(1≤t≤10^4),表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和m(1≤n≤10^5;0≤m≤min(10^5, n×(n-1)/2)),分别表示顶点的数量和边的数量。
- 第二行包含n个整数a_1, a_2, ..., a_n(0≤a_i≤n-1),表示每个顶点的度数要求。
- 接下来的m行,每行包含两个整数v和u(1≤v,u≤n;v≠u),表示一条边的两个顶点。
- 图中没有自环或多重边。
- 所有测试用例的n之和不超过10^5,m之和不超过10^5。
- 输入保证至少存在一个有效的移除序列。

输出格式:
- 对于每个测试用例,输出一个整数,表示“美好”的点对数量。

输入输出样例:
输入样例 #1:
```
4
3 2
1 0 1
2 3
1 2
3 3
1 2 0
1 2
2 3
1 3
5 6
3 0 2 1 0
1 2
4 1
4 2
3 4
2 3
5 1
1 0
0
```
输出样例 #1:
```
1
0
4
0
```题目大意: 你有一个简单无向图,包含n个顶点和m条边。顶点编号为1到n,第i个顶点有权值a_i。你可以删除一些顶点,但只有当顶点i的度数等于a_i时,删除才是合法的。删除一个顶点后,与该顶点相连的所有边也会被删除。一个有效的移除序列p是1到n的一个排列,使得按照p的顺序删除每个顶点都是合法的。如果存在两个有效的移除序列,其中一个序列中x在y之前被删除,另一个序列中y在x之前被删除,且x

加入题单

上一题 下一题 算法标签: