Skip to content

12212: 【原2212】向哥的实验

题目

题目描述

author: 杨欢 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2212

Description

向哥最近在研究树上的一些问题,在他的研究中,经常会碰到关于两个点之间的路径的一些问题,现在他希望你们能够帮他写个程序,来完成这个任务。 初始的时候你有一棵树,树上的每个点上有一个权值,最为这个点的初始权值,你要维护下面的一些操作:

1."1 x a":把树上编号为x的点的权值改为a。

2."2 x y a":把树上编号为x和编号为y的点之间的路径上的点(包括x和y)的权值全部改为a。

3."3 x y a":把树上编号为x和编号为y的点之间的路径上的点(包括x和y)的权值全部去相反数。

4."4 x y a":输出树上编号为x和编号为y的点之间的路径上的点(包括x和y)的权值所组成的序列(按照从x到y的顺序)的最大和,如果结果小于0则输出0。

注:序列的最大和即序列中连续的一段数且这段数和是最大的。

Input Format

第1行:两个正整数n,m,表示树上的点数和操作数。
第2~n行:每行两个正整数x,y,表示在树上点x和y之间有一条边。
第n+1行:n个整数,表示树上每个点的初始权值。
第n+2~n+m+1行:每行一个操作,如题目描述。

Output Format

对于输入中的每个操作4,你都要输出其对应的最大和是多少,每个输出占一行。

Hint

1.朴素的程序很好写,时间不够的话可以考虑写个朴素捞分。
2.数据保证从节点1进行深度优先搜索不会爆栈。

Sample Input

10 10
6 7
6 10
10 4
9 10
9 3
9 8
7 1
8 5
2 10
0 9 2 9 2 1 9 3 -8 0 
2 1 8 5
1 1 -1
4 8 9
2 7 7 1
1 5 6
3 4 4
4 3 4
3 5 8
2 1 9 3
4 2 3

Sample Output

10
12
17

Data Scale

30%: 0 < n <= 1000  0 < m <= 10000    
30%: 0 < n <= 30000 0 < k <= 500000    
40%: 0 < n <= 100000 0 < k <= 400000

Oops! 本题目还没有解答!

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

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

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