Skip to content

11619: 【原1619】Interesting Candies

题目

题目描述

author: fangbohui 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1619

Description

SJTU内有n个糖果机,糖果机之间通过n−1条路相互连通。每个糖果机都有一个值v,表示为xzj提供的糖果的甜度。

由于糖果被频繁的消耗和补充,糖果机的甜度v会时常发生变化。xzj只能从编号为1的糖果机出发,并且每个糖果机至多经过一次。另外,xzj每次出发时会对某个糖果机的糖果有所偏爱,要求路线上必须有那个糖果机。

为xzj规划一个路径,使得路径上的甜度总和最大。

两次询问之间的偏好是独立的,即不会在之后的路径考虑之前的偏好。

Input Format

第1行包含两个整数n,m(1≤n,m≤100000),表示有n个糖果机,m次查询。

接下来n−1行,每行两个整数x和y(1≤x,y≤n),表示编号为x的零食机与编号为y的零食机相连。

接下来一行由n个数组成,表示从编号为1到编号为n的糖果机的初始甜度v(∣v∣≤100000)。

接下来m行,有两种操作:0 x y,表示编号为x的糖果机的价值变为y;1 x,表示询问从编号为1的糖果机出发,必须经过编号为x糖果机的路线中,甜度总和的最大值。

Output Format

m行输出。 每行1个数,代表该次询问的最大值。

Sample Input

6 5
1 2
2 3
1 4
4 5
6 4
7 -5 100 20 -5 -7
1 2
1 4
0 3 -1
1 2
1 6

Sample Output

102
27
2
20

Limits

  • 对于30%的数据,n不超过1000;
  • 对于100%的数据,n不超过100000.
  • 对于所有的数据,保证|v[i]|<=100000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!