#574. 「LibreOJ NOI Round #2」黄金矿工

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zx2003

题目描述

你是一处金矿的主人,并且有若干矿工要来这里挖黄金。

这处宝藏有 n 个可能的藏宝点,这 n 个点构成了一棵有根树的结构。

树上的每条边都是有向的,从父亲指向儿子,并且有个正整数权值 c_i ,表示每有一个矿工从这条边走过,你会收取 c_i 的过路费。

每个矿工 x 会从某一个藏宝点 u 出发,并且有一个正整数权值 P_x ,表示如果你允许他来挖宝,将会获得 P_x 的入场费。

某个藏宝点 u 可能还会出现一块权值为 Q_y 黄金,表示如果有矿工挖取了这个黄金,你会从中提走 Q_y 的利润。

一个矿工 x 挖取一块黄金 y 的收益是 P_x+Q_y+\sum_{e}{c_e} ,其中边 e 在人 x 和黄金 y 的路径上。

注意一个矿工只能挖取一块黄金,一块黄金也只能被一个矿工挖取。一个矿工只能挖取他沿着树上有向边能到的黄金,同一条边在同一个挖取方案中可以被多个人经过

一开始既没有黄金也没有矿工。

我们需要支持 q 次操作,每次操作有两种类型:

  • 1 u v :表示在点 u 上新出现了一个权为 v 的矿工。
  • 2 u v :表示在点 u 上新出现了一块权为 v 的黄金。

你需要在每次操作后算出,如果让某些矿工去挖取黄金,那么可能的最大收益是多少。

注意你并不需要最大化挖到黄金的人数量

输入格式

从标准输入读入数据。

第一行两个整数 n q ,表示树的节点和操作数。

接下来 n-1 行,每行三个正整数 u,v,c ,表示有一条权为 c 的边从点 u 指向点 v

接下来 q 行每行描述一次操作。

输出格式

输出到标准输出。

对于每次操作,输出一个整数表示这次操作执行后的答案。

样例

样例输入 1

5 5
1 2 1
1 3 1
1 4 1
4 5 1
1 3 5
2 3 1
1 4 8
1 1 1
2 1 10

样例输出 1

0
6
6
6
17

样例解释 1

第二次操作后,最优匹配方案是,让第一次操作添加的矿工挖去第二次操作添加的黄金。

第五次操作后,最优匹配方案为,在前一方案的基础上,让第四次操作添加的矿工挖去第五次操作添加的黄金。

样例 2

见下发文件。

样例 3

见下发文件。

数据范围与提示

对于所有数据,保证 n,q \le 10^5 ,并且所有树边的权均为不超过 10^3 的正整数,所有矿工和黄金的权均为不超过 10^8 的正整数。

测试点 n= q= 特殊性质
1 8 C2
2 300
3,4 4 * 10^3
5 ~ 10 10^3 5 * 10^4 C1
11 ~ 13 C2
14,15 10^5 5 * 10^4 A1
16,17 B1
18,19 C1
20 ~ 24 C2
25 10^5

表格中的特殊性质

  • A:第 i 条边从 i 指向 i+1
  • B:第 i 条边从 \lfloor \frac{i+1}{2} \rfloor 指向 i+1
  • C:在树的形态上无特殊约束
  • 1:保证所有 1 操作都在 2 操作之后
  • 2:在操作类型上无特殊约束