bzoj#P4732. 数据交互

数据交互

题目描述

一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据 线则看做一 条树边。两个服务器进行数据交互时,数据会经过连接这两个服务器的路径上的所有服务 器(包括这两个服务器 自身)。每个数据交互请求都有一个非负的重要度,越重要的请求显然需要得 到越高的优先处理权。此外,如果 在某一个时刻存在一条非常重要(可以看作重要度无穷大)、且数 据量巨大的交互请求,则所有被该交互经过的 服务器都会优先处理这条交互并阻塞,从而导致其他通 过这些服务器的交互出现延迟。现在,你作为一个网络系 统的管理员,要监控整个系统的运行状态。 系统的运行也很简单,在每一个时刻,只有可能出现下列二种事件中 的一种: 1、在某两个服务器之间出现一条新的数据交互请求; 2、某个数据交互请求结束; 我们假设这些事件中的交互请求的数据量都足够小。你的任务是在每一个时刻的事件结束后,求出: 如果突然出现一条非常重要、且数据量巨大的交互请求 那么因其造成延迟的数据交互请求的重要度之和最大可能是多少?

输入格式

输入的第一行包含二个正整数N,M,分别表示服务器的个数、事件(时刻)的个数。 接下来N?1行,每行两个整数u,v,描述一条树边。u和v是服务器的编号,服务器编号1…n。 接下来M行,按发生时刻依次描述每一个事件;即第i行(i=1,2,3,…,m)描述时刻i发生的事件。 事件的描述有两种:

  • u v w 服务器u和v之间出现了一条重要度为w的数据交互请求 ? t 时刻tt出现的数据交互请求结束 1≤N,M≤10^5,所有的输入数据均为 int 范围内的非负整数。保证输入合法。

输出格式

输出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

7
11
4
7
10
9

提示

没有写明提示

题目来源

没有写明来源