#P1505. [国家集训队] 旅游

    ID: 498 Type: RemoteJudge 1000ms 256MiB Tried: 7 Accepted: 3 Difficulty: 5 Uploaded By: Tags>WC/CTSC/集训队树链剖分

[国家集训队] 旅游

题目背景

Ray 乐忠于旅游,这次他来到了 T 城。T 城是一个水上城市,一共有 nn 个景点,有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本,T 城的任意两个景点之间有且只有一条路径。换句话说, T 城中只有 n1n-1 座桥。

Ray 发现,有些桥上可以看到美丽的景色,让人心情愉悦,但有些桥狭窄泥泞,令人烦躁。于是,他给每座桥定义一个愉悦度 ww,也就是说,Ray 经过这座桥会增加 ww 的愉悦度,这或许是正的也可能是负的。有时,Ray 看待同一座桥的心情也会发生改变。

现在,Ray 想让你帮他计算从 uu 景点到 vv 景点能获得的总愉悦度。有时,他还想知道某段路上最美丽的桥所提供的最大愉悦度,或是某段路上最糟糕的一座桥提供的最低愉悦度。

题目描述

给定一棵 nn 个节点的树,边带权,编号 0n10 \sim n-1,需要支持五种操作:

  • C i w 将输入的第 ii 条边权值改为 ww
  • N u vu,vu,v 节点之间的边权都变为相反数;
  • SUM u v 询问 u,vu,v 节点之间边权和;
  • MAX u v 询问 u,vu,v 节点之间边权最大值;
  • MIN u v 询问 u,vu,v 节点之间边权最小值。

保证任意时刻所有边的权值都在 [1000,1000][-1000,1000] 内。

输入格式

第一行一个正整数 nn,表示节点个数。
接下来 n1n-1 行,每行三个整数 u,v,wu,v,w,表示 u,vu,v 之间有一条权值为 ww 的边,描述这棵树。
然后一行一个正整数 mm,表示操作数。
接下来 mm 行,每行表示一个操作。

输出格式

对于每一个询问操作,输出一行一个整数表示答案。

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2
3
2
1
-1
5
3

提示

【数据范围】

对于 100%100\% 的数据,1n,m2×1051\le n,m \le 2\times 10^5

2020.02.04 修正了一点数据的错误
2020.03.14 加入了一组 hack 数据
2020.11.26 加入了一组 hack 数据 By @_Leaving