P12584 「KTSC 2019 R1」产油国

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include long long findEdges(int N, std::vector A, std::vector B); ``` 题目译自 [2019년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2019/) T3「[산유국](https://assets.ioikorea.kr/ioitst/2019/1/oil/oil_statement.pdf)」

阿塞拜疆是一个地下资源丰富的国家，盛产石油，国民可以非常廉价地使用汽油。 阿塞拜疆的首都巴库有 $N$ 个十字路口和 $M+N-1$ 条双向道路。巴库是一座南北向狭长的城市。十字路口按南北方向排成一条直线，从最北端的十字路口开始，依次编号为 $1$ 到 $N$。 城市中有旧路和新建的道路。共有 $N-1$ 条旧路，分别连接编号为 $i (1 \leq i < N)$ 的十字路口和编号为 $i+1$ 的十字路口。此外，还有 $M$ 条新建道路，每条新建道路连接一对不同的、未被旧路连接的十字路口。任意一对十字路口之间最多只有一条道路连接。 由于近期财政状况不佳，巴库决定在部分道路上设置收费站来收取通行费。为了避免市民的不满，只会在恰好两条道路上收取通行费。每当一辆车通过收费站时，需要支付 $1$ 马纳特（阿塞拜疆的货币单位）的通行费。如果一辆车经过两个收费站，那么需要支付 $2$ 马纳特。 每个十字路口都有 $N-1$ 辆汽车。每个十字路口的汽车都会前往除当前所在十字路口外的其他不同十字路口。司机在从十字路口 $u$ 到十字路口 $v$ 时，会选择通行费最少的路径（因为在这个国家汽油非常便宜）。 当所有汽车都到达目的地后，请编写一个程序，找出应该在哪两条道路上设置收费站，才能使收取的通行费总额最大。 你需要实现以下函数： `long long findEdges(int N, int A[], int B[]);` 该函数只会在程序开始时被调用一次，用于提供十字路口和道路的结构信息。参数说明如下： `N`：十字路口的数量。 `A` 和 `B`：大小为 `M` 的数组，表示新建的 $M$ 条道路。其中，`A[i]` 和 `B[i]` 表示第 $i (0 \leq i < M)$ 条新建道路连接的两个十字路口编号。 你的任务是根据给定的十字路口和道路信息，计算在两条道路上设置收费站所能收取的最大通行费总额，并返回这个值。 函数必须按照上述描述进行操作。你可以在程序中创建和使用其他函数，但不得进行任何输入输出操作或访问其他文件。

示例评测程序按照以下格式读取输入： - 第 $1$ 行：两个整数 $N$ 和 $M$，分别表示十字路口的数量和新建道路的数量。 - 接下来的 $M$ 行：每行两个自然数，表示一条新建道路连接的两个十字路口编号。

示例评测程序会输出你的代码中 `findEdges()` 函数返回的值。

### 样例说明 #1 | 调用 | 结果 | | :----------: | :----------: | | `findEdges(4, {3, 2, 1}, {1, 4, 4})` | 函数被调用，返回值 $0$ | ### 数据范围 | 子任务 | 分值 | 约束 | | :----------: | :----------: | :----------: | | $1$| $10$| $3 \leq N \leq 100，0 \leq M \leq 100$| |$2$|$13$|$3 \leq N \leq 2000，0 \leq M \leq 2000$| |$3$|$48$|$3 \leq N \leq 10^5，0 \leq M \leq 10^5$| |$4$|$29$|$3 \leq N \leq 5\cdot 10^5，0 \leq M \leq 5\cdot 10^5$|