[R36F]运输线路 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

在一个由 $n$ 个城市和 $n-1$ 条双向道路构成的国家中，城市之间的连接形成了一棵树。一家物流公司获得了 $m$ 条独家运输线路的合同。

每条线路 $i$ 都定义了一个起点 $w_i$，以及两个潜在的目的地 $u_i$ 和 $v_i$（保证 $u_i \not= v_i$）。合同保证了起点 $w_i$ 恰好位于 $u_i$ 和 $v_i$ 之间的唯一简单路径上。对于每条线路，公司有以下三种操作选择：

1. 忽略此线路：不执行任何运输，获得价值 $0$。
2. 单向运输: 将货物从 $w_i$ 运送到 $u_i$ 或者 $v_i$ 中的任意一个。完成此项任务可以获得 $a_i$ 的价值。选择运到 $u_i$ 会占用路径 $w_i \to u_i$ 上的所有城市（包括端点），运到 $v_i$ 则会占用路径 $w_i \to v_i$ 上的所有城市。
3. 双向运输: 将货物从 $w_i$ 同时运送到 $u_i$ 和 $v_i$。完成此项任务可以获得 $b_i$ 的价值。这会同时占用路径 $w_i \to u_i$ 和 $w_i \to v_i$ 上的所有城市。

为了保证运输通畅，规定任何一个城市最多只能被一条被选中的运输线路所占用。如果一个城市位于某条被选定执行任务的线路上，它就被视为“已占用”。

你的任务是帮助物流公司选择一部分线路并为它们分配合适的运输操作，使总价值最大。

格式

输入格式

输入的第一行包含两个整数 $n, m$，分别表示城市的数量和运输线路的数量。

接下来 $n-1$ 行，每行两个整数 $x, y$，表示城市 $x$ 和 $y$ 之间有一条道路。城市编号为 $1$ 到 $n$。

接下来 $m$ 行，每行五个整数 $u_i, v_i, w_i, a_i, b_i$，描述一条运输线路。

输出格式

输出一个整数，表示可以获得的最大总价值。

样例

样例输入 #1

5 3
1 2
1 3
2 4
2 5
3 4 3 1 10
4 5 2 2 8
2 3 1 3 4

样例输出 #1

11

数据规模

对于 $100\%$ 的数据，$3 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 10^5$，$1 \leq a_i, b_i \leq 10^9$。输入保证形成一棵树，且对于每条线路 $i$，$w_i$ 均在 $u_i, v_i$ 的简单路径上，且 $u_i \not = v_i$ 。

本题采用子任务捆绑，你需要通过每个子任务的所有测试数据才能得到对应的分数。

子任务 $1$ ($20$ 分)：$3 \leq n \leq 20$，$1 \leq m \leq 10$。

子任务 $2$ ($20$ 分)：$3 \leq n \leq 1000$，$1 \leq m \leq 1000$。

子任务 $3$ ($60$ 分)：无特殊限制。