#1157. [国家集训队] 旅游
[国家集训队] 旅游
题目背景
Ray 乐忠于旅游,这次他来到了 T 城。T 城是一个水上城市,一共有 个景点,有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本,T 城的任意两个景点之间有且只有一条路径。换句话说, T 城中只有 座桥。
Ray 发现,有些桥上可以看到美丽的景色,让人心情愉悦,但有些桥狭窄泥泞,令人烦躁。于是,他给每座桥定义一个愉悦度 ,也就是说,Ray 经过这座桥会增加 的愉悦度,这或许是正的也可能是负的。有时,Ray 看待同一座桥的心情也会发生改变。
现在,Ray 想让你帮他计算从 景点到 景点能获得的总愉悦度。有时,他还想知道某段路上最美丽的桥所提供的最大愉悦度,或是某段路上最糟糕的一座桥提供的最低愉悦度。
题目描述
给定一棵 个节点的树,边带权,编号 ,需要支持五种操作:
C i w
将输入的第 条边权值改为N u v
将 节点之间的边权都变为相反数SUM u v
询问 节点之间边权和MAX u v
询问 节点之间边权最大值MIN u v
询问 节点之间边权最小值
保证任意时刻所有边的权值都在 内。
输入格式
第一行一个正整数 ,表示节点个数。 接下来 行,每行三个整数 ,表示 之间有一条权值为 的边,描述这棵树。 然后一行一个正整数 ,表示操作数。 接下来 行,每行表示一个操作。
输出格式
对于每一个询问操作,输出一行一个整数表示答案。
提示
【数据范围】
对于 的数据,。
2020.02.04 修正了一点数据的错误 2020.03.14 加入了一组 hack 数据 2020.11.26 加入了一组 hack 数据 By @_Leaving