← 返回题目列表

Codeforces · 1787/G

G. 七彩树又来了

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

给出 $$$n$$$ 个节点的边加权树,每条边都以某种颜色着色。该树的每个节点都可以被阻塞或解除阻塞,所有节点最初都是解除阻塞的。

简单路径是图中没有重复节点的路径。路径的长度定义为路径上所有边的权重之和。

当一条路径是由相同颜色 $$$c$$$ 的边组成的简单路径,所有颜色 $$$c$$$ 的边都在这条路径上,并且路径上的每个节点都畅通无阻时,这条路径就是好的。

需要操作$$$2$$$种查询:

1. 阻塞一个节点,
2. 解锁节点。

每次查询后,打印所有好路径中的最大长度。如果没有好的路径,则打印$$$0$$$。

输入

第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \leq n,q \leq 2\cdot 10^5$$$) — 节点数和查询数。

接下来是 $$$n-1$$$ 行,每行包含四个整数 $$$u$$$、$$$v$$$、$$$w$$$ 和 $$$c$$$ ($$$1 \leq u,v,w,c \leq n$$$; $$$u \not = v$$$),表示连接节点 $$$u$$$ 和节点的加权边$$$v$$$ 重量 $$$w$$$ 和颜色 $$$c$$$。保证这些边形成一棵树。

接下来是 $$$q$$$ 行,每行包含两个整数 $$$p$$$ 和 $$$x$$$($$$p = 0$$$ 或 $$$p = 1$$$, $$$1\leq x\leq n$$$),表示一个查询:

1. 如果$$$p = 0$$$,则阻止节点$$$x$$$。保证此时不被阻塞;
2. 如果$$$p = 1$$$,则解锁节点$$$x$$$。这个时候保证是被堵住的。

输出

对于每个查询,打印好路径的最大长度。如果没有好的路径,则打印$$$0$$$。

示例

输入 #1

5 4
4 1 3 4
5 2 4 4
3 1 3 2
1 2 5 1
0 4
0 3
0 2
1 3

输出 #1

5
5
0
3

输入 #2

5 5
4 1 4 4
4 5 2 2
3 1 2 4
3 2 3 1
0 3
0 4
1 3
1 4
0 1

输出 #2

2
0
3
6
3

输入 #3

6 9
3 2 2 3
2 4 4 2
3 1 5 5
6 4 3 2
5 3 1 3
0 2
0 4
0 5
0 6
1 2
1 4
1 5
0 3
1 6

输出 #3

5
5
5
5
5
5
5
0
7

输入#4

1 2
0 1
1 1

输出#4

0
0