Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom3月前

05/17
22:27
树链剖分 线段树

[bzoj 4127] Abs

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给定一棵树,设计数据结构支持以下操作

1 u v d 表示将路径 (u,v) 加d

2 u v 表示询问路径 (u,v) 上点权绝对值的和

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行两个整数n和m,表示结点个数和操作数

接下来一行n个整数a_i,表示点i的权值

接下来n-1行,每行两个整数u,v表示存在一条(u,v)的边

接下来m行,每行一个操作,输入格式见题目描述

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每个询问输出答案

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

10
13
9

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于100%的数据,n,m <= 10^5 且 0<= d,|a_i|<= 10^8

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

树链剖分

因为 d>=0 ,所以每个a[i]至多改变符号一次,遇上要改变的时候直接在线段树上暴力改

 

[bzoj 4127] Abs