1256. 数据交互
题目描述
一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据交互时,数据会经过连接这两个服务器的路径上的所有服务器(包括这两个服务器自身)。
每个数据交互请求都有一个非负的重要度,越重要的请求显然需要得到越高的优先处理权。此外,如果在某一个时刻存在一条非常重要(可以看作重要度无穷大)、且数据量巨大的交互请求,则所有被该交互经过的服务器都会优先处理这条交互并阻塞,从而导致其他通过这些服务器的交互出现延迟。
现在,你作为一个网络系统的管理员,要监控整个系统的运行状态。系统的运行也很简单,在每一个时刻,只有可能出现下列二种事件中的一种:
- 在某两个服务器之间出现一条新的数据交互请求;
- 某个数据交互请求结束。
我们假设这些事件中的交互请求的数据量都足够小。你的任务是在每一个时刻的事件结束后,求出:如果突然出现一条非常重要、且数据量巨大的交互请求,那么因其造成延迟的数据交互请求的重要度之和最大可能是多少?
输入
第一行,包含二个正整数 \(N, M\),分别表示服务器的个数、事件(时刻)的个数。
接下来 \(N-1\) 行,每行两个整数 \(u, v\),描述一条树边。\(u\) 和 \(v\) 是服务器的编号,服务器编号 \(1,\dots,n\)。
接下来 \(M\) 行,按发生时刻依次描述每一个事件;即第 \(i\) 行(\(i=1,2,3,\dots,m\))描述时刻 \(i\) 发生的事件。事件的描述有两种:
+ u v w
:服务器 \(u\) 和 \(v\) 之间出现了一条重要度为 \(w\) 的数据交互请求;- t
:时刻 \(t\) 出现的数据交互请求结束。
输出
输出 \(M\) 行,每行一个整数,依次描述在每个事件后,如果突然出现一条非常重要、且数据量巨大的交互请求,
那么因其造成延迟的数据交互请求的重要度之和的最大值。如果此时没有任何数据交互请求,输出 \(0\)。
样例一
输入
5 6
1 2
2 4
4 3
2 5
+ 1 4 7
+ 5 5 4
- 1
+ 3 4 3
+ 1 1 6
- 2
输出
11
4
7
10
9
限制与约定
对于 \(30\%\) 的数据,有\(1 \leq N, M \leq 100\)。
另有 \(30\%\) 的数据,没有第二类事件,即所有请求都不会结束。
对于 \(100\%\) 的数据,有 \(1 \leq N, M \leq 10^5\),所有的输入数据均为 int
范围内的非负整数。
保证输入合法。
时间限制:\(3\texttt{s}\)
空间限制:\(1024\texttt{MB}\)
信息
- ID
- 1256
- 难度
- (无)
- 分类
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者