#1695. 小 H 分糖果
小 H 分糖果
小 H 分糖果
题目描述
标题: 小 H 分糖果 - Problem - QOJ.ac
#5094. 小 H 分糖果
The problem was used in the following contests:
小 H 居住的国度形成一棵树。树是 n 个点 n−1 条边的连通图,每一个节点上是一个城市,编号为 i 的城市内居住着一位小朋友,这位小朋友期待在万圣节收到 ai 颗糖果。
作为万圣老人,小 H 将计划他的万圣节行程,一种可能的行程是携带 m 个糖果从编号为 u 的城市出发,通过唯一的最短路走向 v 号城市,并给予居住在这条路径上(包括 u,v)的所有小朋友一些糖果(可能某些小朋友没有收到糖果)。
在小 H 分发糖果之后,所有的小朋友(包括路径之外的)将会把收到的糖果数量 ai′ 与自己期待的糖果数量 ai 进行比较,称一位小朋友的悲哀度为
max{0,ai−ai′}2
那么小 H 希望最小化所有小朋友的悲哀度之和。
现在按照时间顺序,依次发生 q 个事件。每个事件有以下两种可能:
1 u b:居住在 u 号节点的小朋友改变了主意,将他期待收到的糖果数量变为 b,也即将 au 赋值为 b。注意这个过程会影响后续的事件。2 u v m:小 H 模拟一个万圣节行程计划,请你告诉他最小可能的悲哀度总和是多少。注意这个过程不会影响后续的事件。
输入格式
第一行两个正整数 n,q 表示城市个数与事件个数。
接下来 n−1 行,每行两个正整数 u,v 表示树的一条边。保证不会重复给出同一条边。
接下来一行 n 个非负整数 a1,a2,…,an,表示每位小朋友期待的糖果数目。
接下来 q 行每行可能为 1 u b 与 2 u v m 两种形式之一,含义如上所述。
输出格式
对于每一个第二类事件,输出一行一个非负整数表示最小的悲哀度总和。
样例一
input
3 3
1 2
1 3
1 4 3
2 2 3 5
1 3 4
2 2 3 5
output
3
6
限制与约定
对于所有数据,1≤n,q≤105, 0≤ai,b≤109, 0≤m≤1014, 1≤u,v≤n。
子任务 1(10%):n,q≤1000,m≤1000。
子任务 2(15%):n,q≤1000。
子任务 3(15%):树的形态是一条链,即树中每个节点的度数 ≤2。
子任务 4(60%):无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 3
1 2
1 3
1 4 3
2 2 3 5
1 3 4
2 2 3 5
3
6