/ Vijos / 题库 /

小白逛公园加强版

小白逛公园加强版

背景

Crash觉得小白逛公园有点简单了,稍微加强了一下……

描述

小新经常陪小白去公园玩,也就是所谓的遛狗啦……在小新家附近有n个公园,这些公园通过一些路径相连,并保证每两个公园之间有且仅有一条通路相连(也就是说这是一棵树),小白早就看花了眼,自己也不清楚该去哪些公园玩了。
小白对每个公园都有一个评价(可正可负),并且它只会让小新做两件事:
1. 询问公园a到公园b路径上最大连续公园的评价和,就是说我们把公园a到公园b路径上的公园(包括a和b)排成一条直线,那么小白希望知道一段连续的公园的评价和最大为多少。

2. 修改公园a到公园b路径上(包括a和b)每个公园的评价值。

小新现在已经处理不了n超过10的情况,因此请你来帮忙……

格式

输入格式

第一行有一个自然数,表示n
第二行有n个自然数,表示一开始小白对每个公园的评价(评价值的绝对值不超过10000)
下面有n-1行,每行两个数a和b,表示公园a和公园b直接由道路相连
再下面一行有一个自然数,表示m
最后m行,每行第一个数k表示要执行的操作。如果k为1,那么后面有两个自然数a和b,表示询问公园a到公园b路径上(包含a和b)最大的连续公园评价和(如果这条路径上每个公园的评价都为负数,那么最大连续和为0)。如果k为2,那么后面有三个自然数a、b和c,表示把公园a到公园b路径上所有的公园(包括a和b)的评价都修改为c。(c的绝对值不超过10000)

输出格式

对于每次询问,输出最大连续和。(用空格隔开,最后要有换行符)

样例1

样例输入1

5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5

样例输出1

5 9

限制

小数据1s,大数据2s
(时间是足够的……)

提示

对于30%的数据:n,m <= 100
对于70%的数据:n,m <= 50000
对于100%的数据:n,m <= 100000

信息

ID
1620
难度
8
分类
树结构 | 树链剖分 点击显示
标签
(无)
递交数
767
已通过
109
通过率
14%
上传者

相关

在下列训练计划中:

RP++分类题库