#1695. 小 H 分糖果

    ID: 1695 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1047来源:qoj.ac数据:公开样例最短路径树上算法差分

小 H 分糖果

小 H 分糖果

题目描述

标题: 小 H 分糖果 - Problem - QOJ.ac

#5094. 小 H 分糖果

Statistics

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