Colorful Tree Again

题意翻译

### 题目描述 给定一棵有 $n$ 个节点的树，边有边权和颜色。每个点有被摧毁和不被摧毁两种状态，初始所有点都没被摧毁。 一条简单路径指图中没有重复节点的路径。简单路径的长度定义为路径上所有边的边权之和。 定义一条简单路径是好的，当且仅当路径仅有某一种颜色 $c$ 构成，且所有颜色为 $c$ 的边都在这条简单路径里，且路径上所有节点都没被摧毁。 你需要处理两种操作： 1. 摧毁一个节点； 2. 修复一个节点。 每个操作之后，你都需要输出最长的好的路径长度。若没有输出 $0$。 ~~写了 3 次样例解释全被删了 QAQ~~ ### 输入格式 第一行两个正整数 $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$ 即 $1$，$1\le x\le n$）表示一个询问： 1. 若 $p = 0$，表示摧毁节点 $x$，保证此时 $x$ 没被摧毁； 2. 若 $p = 1$，表示修复节点 $x$，保证此时 $x$ 已被摧毁。 ### 输出格式 每个询问后，输出最长的好的路径的长度。若没有输出 $0$。

题目描述

An edge-weighted tree of $ n $ nodes is given with each edge colored in some color. Each node of this tree can be blocked or unblocked, all nodes are unblocked initially. A simple path is a path in a graph that does not have repeating nodes. The length of a path is defined as the sum of weights of all edges on the path. A path is good when it is a simple path consisting of edges of the same color $ c $ , all edges of color $ c $ are on this path, and every node on the path is unblocked. You need to operate $ 2 $ kinds of queries: 1. block a node, 2. unblock a node. After each query, print the maximum length among all good paths. If there are no good paths, print $ 0 $ .

输入输出格式

输入格式

The first line contains two integers $ n $ , $ q $ ( $ 1 \leq n,q \leq 2\cdot 10^5 $ ) — the number of nodes and the number of queries. Then $ n-1 $ lines follow, each containing four integers $ u $ , $ v $ , $ w $ and $ c $ ( $ 1 \leq u,v,w,c \leq n $ ; $ u \not = v $ ), denoting a weighted edge connecting node $ u $ and node $ v $ with weight $ w $ and color $ c $ . It is guaranteed that these edges form a tree. Then $ q $ lines follow, each containing two integers $ p $ and $ x $ ( $ p = 0 $ or $ p = 1 $ , $ 1\leq x\leq n $ ), denoting a query: 1. if $ p = 0 $ , block the node $ x $ . It's guaranteed that it's not blocked at this time; 2. if $ p = 1 $ , unblock the node $ x $ . It's guaranteed that it's blocked at this time.

输出格式

For each query, print the maximum length of a good path. If there are no good paths, print $ 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

**题目大意：**

有一棵包含 $ n $ 个节点的树，每条边都有边权和颜色。每个节点可以处于被摧毁或未被摧毁的状态，所有节点初始时都是未被摧毁的。

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

如果一条简单路径仅由一种颜色 $ c $ 的边组成，且所有颜色为 $ c $ 的边都在这条路径上，同时路径上的所有节点都未被摧毁，则称这条路径是好的。

需要处理两种操作：

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 \neq v $），表示一条树边 $ (u,v) $，边权为 $ w $，颜色为 $ c $。保证这些边构成一棵树。

再接下来 $ q $ 行，每行两个正整数 $ p $ 和 $ x $（$ p $ 为 $ 0 $ 或 $ 1 $，$ 1 \leq x \leq n $），表示一个询问：

1. 如果 $ p = 0 $，表示摧毁节点 $ x $。保证此时 $ x $ 没被摧毁；
2. 如果 $ p = 1 $，表示修复节点 $ x $。保证此时 $ x $ 已被摧毁。

**输出格式：**

对于每个询问，输出最长的好的路径的长度。如果没有好的路径，则输出 $ 0 $。**题目大意：** 有一棵包含 $ n $ 个节点的树，每条边都有边权和颜色。每个节点可以处于被摧毁或未被摧毁的状态，所有节点初始时都是未被摧毁的。 简单路径是指没有重复节点的路径。路径的长度定义为路径上所有边的边权之和。 如果一条简单路径仅由一种颜色 $ c $ 的边组成，且所有颜色为 $ c $ 的边都在这条路径上，同时路径上的所有节点都未被摧毁，则称这条路径是好的。 需要处理两种操作： 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 \neq v $），表示一条树边 $ (u,v) $，边权为 $ w $，颜色为 $ c $。保证这些边构成一棵树。 再接下来 $ q $ 行，每行两个正整数 $ p $ 和 $ x $（$ p $ 为 $ 0 $ 或 $ 1 $，$ 1 \leq x \leq n $），表示一个询问： 1. 如果 $ p = 0 $，表示摧毁节点 $ x $。保证此时 $ x $ 没被摧毁； 2. 如果 $ p = 1 $，表示修复节点 $ x $。保证此时 $ x $ 已被摧毁。 **输出格式：** 对于每个询问，输出最长的好的路径的长度。如果没有好的路径，则输出 $ 0 $。