题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Bajholmska Firma Transportowa

拜霍尔姆运输公司租用了 $n$ 个仓库，每个仓库位于拜霍尔姆的一个岛屿上。这些岛屿通过桥梁相连，任意两个岛屿之间有且仅有一条路径可达（可能需要经过其他岛屿）。此外，每个桥梁都有车辆最大重量的限制。

Bajteusz 是公司的一名司机，负责在仓库之间运输货物。每次运输总是选择最短路径。Bajteusz 对建筑颇有兴趣，他认为拜霍尔姆的一些桥梁是建筑珍品，因此非常乐意经过这些桥梁。他将经过至少一座此类桥梁的运输路线称为迷人路线。

运输公司运送的货物种类繁多，因此 Bajteusz 驾驶的车辆重量经常变化。他很好奇车辆重量会如何影响他可能执行的运输任务数量（即在两个岛屿之间运输）。请帮助他编写一个程序，计算给定车辆重量下，连接两座仓库的最短路径为迷人路线且车辆重量未超过路径上任意桥梁限制的路线对数量。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $q$ $(2 \leq n \leq 100000, 1 \leq q \leq 200000)$，分别表示拜霍尔姆的岛屿数量和查询次数。岛屿编号为从 $1$ 到 $n$ 的整数。

接下来的 $n-1$ 行描述拜霍尔姆的桥梁：第 $i$ 行包含四个整数 $u_{i}, v_{i}, m_{i}, a_{i}$ $(1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i}, 1 \leq m_{i} \leq 10^{9}, 0 \leq a_{i} \leq 1)$，表示第 $i$ 座桥梁连接编号为 $u_{i}$ 和 $v_{i}$ 的岛屿，允许通过的最大车辆重量为 $m_{i}$，$a_{i}=1$ 表示 Bajteusz 认为该桥梁是建筑珍品。

接下来的 $q$ 行描述查询：第 $j$ 行包含一个整数 $w_{j}$ $(1 \leq w_{j} \leq 10^{9})$，表示第 $j$ 次查询中车辆的重量。

输出格式

输出应包含 $q$ 行：第 $j$ 行应为一个整数，表示输入中第 $j$ 次查询的答案，即 Bajteusz 驾驶重量为 $w_{j}$ 的车辆能够通过的迷人路线数量。

6 5
1 2 2 0
2 3 6 1
2 5 8 1
5 4 9 0
5 6 4 0
3
5
10
7
8

7
5
0
2
2

附加样例

1. $n=10$，$q=10$；岛屿 $i$ 与 $i+1$ 通过桥梁相连，桥梁重量限制为 $i$ $(1 \leq i \leq 9)$，重量限制为偶数的桥梁是建筑珍品；查询依次为重量 $1, 2, 3, \ldots, 10$；
2. $n=100000$，$q=1$；所有桥梁均为建筑珍品，且从岛屿 $1$ 连接到岛屿 $i$ $(2 \leq i \leq n)$。

数据范围与提示

详细子任务附加限制及分值如下表所示。