题目类型说明

这是一道提交函数题。原题要求你实现函数：

std::vector<int> solve(
    std::vector<std::pair<int, int>> R,
    std::vector<long long> D,
    std::vector<int> S,
    std::vector<int> T,
    std::vector<bool> I
);

其中：

• R：长度为 N-1 的边集，R[j] = {U_j, V_j} 表示一条无向道路；
• D：长度为 M，D_i 表示第 i 位派对参与者开始旅行的日期；
• S：长度为 M，S_i 表示第 i 位参与者的起点城市；
• T：长度为 M，T_i 表示第 i 位参与者的终点城市；
• I：长度为 M，I_i 表示第 i 位参与者在旅行开始时是否已感染，1 表示感染，0 表示未感染。

函数需要返回一个长度为 M 的数组，第 i 个元素表示：第 i 位参与者在整个派对旅行中，有多少个夜晚处于感染状态。

下文同时给出原题的本地评测器输入输出格式，便于改造成标准输入输出题。

题目描述

Slopia 国有 N 个城市，城市之间由 N-1 条双向道路连接，保证整张图是一棵树，也就是说任意两个城市之间都可以只通过道路互相到达。

政府追踪到了 M 位派对参与者的完整计划。对于第 i 位参与者，已知：

• 其开始旅行的日期为 D_i；
• 起点城市为 S_i；
• 终点城市为 T_i；
• 旅行开始时是否已经感染，记为 I_i。

他们的旅行方式如下：

• 在日期 D_i 的晚上到达城市 S_i，并在该城市参加派对；
• 之后每天沿着从 S_i 到 T_i 的最短路径前进，每天走过恰好一条道路；
• 每到一个城市的晚上，都会在该城市参加派对；
• 在 T_i 参加完派对后的第二天早晨离开 Slopia，结束旅行。

感染传播规则如下：

• 如果某个夜晚，在同一个城市参加派对的人中至少有一人已感染，那么该夜晚在这个城市参加派对的所有人都会被感染；
• 感染不会治愈，一旦感染，在其余旅行过程中都会一直保持感染状态。

请你求出每位参与者在自己的旅行过程中，有多少个夜晚是以感染状态度过的。

约束条件

• 1 <= N, M <= 150000
• 0 <= D_i <= 10^12
• 0 <= U_j, V_j, S_i, T_i < N
• I_i ∈ {0,1}

子任务

只有当该子任务及其所依赖的子任务全部通过时，才能获得对应分数。

本地评测器

输入格式

• 第 1 行：两个整数 N M
• 接下来 N-1 行：每行两个整数 U_j V_j
• 接下来 M 行：每行四个整数 D_i S_i T_i I_i

输出格式

输出 M 行，第 i 行一个整数，表示第 i 位参与者处于感染状态的夜晚数。

样例

输入

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

输出

6
0
4
3
0

样例说明

样例中的城市结构如原题附图所示。

若把每位参与者在每一天所在的城市列成表格，并把其已经感染的日期加粗，就能得到原题中的说明图表。最终 5 位参与者分别有 6, 0, 4, 3, 0 个夜晚处于感染状态。