#P13860. [2026备战省选]优化采购

    ID: 13061 传统题 1000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600数据结构线段树树形DP动态规划可持久化

[2026备战省选]优化采购

【题目描述】

给定一棵nn个点,以11为根的二叉树,每个点要么没有儿子要么有两个儿子,第ii 个点有非负点权aia_i。

现在由深至浅地考虑每个节点uu,计算其新权值bub_u:

•若uu没有儿子,bu←aub_u←a_u

•若其两个儿子的编号分别为x,yx, y,则bu←au+∣bx−by∣b_u←a_u+|b_x−b_y|。

现在有qq次询问,每次修改一个点权aua_u,问修改之后根节点的新权值b1b_1。

【输入格式】

第一行一个正整数nn,表示树的点数。

接下来nn行,第ii行两个非负整数li,ril_i,r_i,分别表示点i的左右儿子的编号,若ii没 有儿子,则li=ri=0l_i=r_i=0。

第n+2n+2行nn个非负整数,分别表示a1,a2,⋅⋅⋅,ana_1,a_2,··· ,a_n。

第n+3n+3行一个正整数qq,表示询问数量。

接下来qq行,每行两个整数u,xu,x,表示将节点uu的权值aua_u改为xx。

【输出格式】

对于每个询问,输出一行一个非负整数表示答案。

【样例1输入】

5 
2 3  
4 5 
0 0 
0 0 
0 0 
1 2 3 4 5 
3 
1 1 
1 10
5 0

【样例1输出】

1  
10  
13 

【数据范围】

对于所有数据,1≤n,q≤105,ai≥01≤n, q≤10^5,a_i≥0;记LL为aia_i在任意时刻的最大值,保证 L≤20L≤20。

测试点编号 n≤n \le q≤q \le L≤L \le 特殊性质
11 10310^3 2020 无无
2∼32 \sim 3 10510^5 AA
4∼54 \sim 5 11 无无
6∼76 \sim 7 55
88 5×1045 \times 10^4 2020
9∼109 \sim 10 10510^5

特殊性质A:树的非叶节点构成一条链,且li=i+1,ri=n+12+il_i=i+1,r_i=\frac{n+1}{2}+i.