← 返回题目列表

Codeforces · 593/D

D. 欢乐树派对

中文机器翻译题面 查看原题

博格丹今天过生日,妈妈送给他一棵由 n 个顶点组成的树。对于树 i 的每条边,上面都写有一些数字 xi 。如果您忘记了,树是一个没有循环的连通无向图。礼物送完后,陆续有m位客人来到博格丹的聚会上。当第 i 位客人到来时,他执行以下两种可能操作之一:

1. 选择一些数字 yi 和两个顶点 ai 和 bi。之后,他使用最短路径沿着树的边从顶点ai移动到顶点bi(当然,这样的路径在树中是唯一的)。每次他沿着某条边 j 移动时,他都会将当前的数字 yi 替换为 $$y_i = \left\lfloor \frac{y_i}{x_j} \right\rfloor$$,即整数除法 yi div xj 的结果。
2. 选择某个边 pi 并将其中写入的值 xpi 替换为某个正整数 ci < xpi。

由于博格丹关心他的客人,他决定简化流程。编写一个程序,执行客人请求的所有操作,并输出第一种类型的每个 i 的结果值 yi 。

输入

输入的第一行包含整数 n 和 m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000) - 分别是 Bogdan 的妈妈授予他的树中的顶点数和参加聚会的客人数。

接下来的 n - 1 行包含边的描述。其中第 i 行包含三个整数 ui、vi 和 xi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ xi ≤ 1018),表示连接顶点 ui 和 vi 的一条边,上面最初写有数字 xi。

以下 m 行描述了博格丹的客人要求的操作。每个描述包含三个或四个整数,并具有两种可能的形式之一:

- 1 ai bi yi 对应一位客人,选择第一种操作。
- 2 pi ci 对应一位客人,选择第二种操作。

输出

对于每个选择第一种操作的客人,通过ai到bi的路径打印处理值yi的结果。

示例

输入 #1

6 6
1 2 1
1 3 7
1 4 4
2 5 5
2 6 2
1 4 6 17
2 3 2
1 4 6 17
1 5 5 20
2 4 1
1 5 1 3

输出 #1

2
4
20
3

输入 #2

5 4
1 2 7
1 3 3
3 4 2
3 5 5
1 4 2 100
1 5 4 1
2 2 2
1 1 3 4

输出 #2

2
0
2

注意

最初,树看起来像这样: 第一个查询的响应是: $$\left\lfloor \frac{\left\lfloor \frac{17}{4} \right\rfloor}{2} \right\rfloor$$ = 2第三条边更改后,树看起来像这样: 第二个查询的响应是: $$\left\lfloor \frac{\left\lfloor \frac{17}{2} \right\rfloor}{2} \right\rfloor$$ = 4在第三个查询中,初始顶点和最终顶点重合,即答案将是初始数字 20。在第四条边发生变化后,树如下所示: 在最后一个查询中,答案将是: $$\left\lfloor \frac { 3 } { 1 } \right\rfloor$$ = 3