跟隔壁的雨天的尾巴 (大佬代码实现原理参照)异常相似
线段树合并入门
1.Analysis
某条路线对当前节点x有贡献时只可能是
x在s到t的路线上(即s到lca到t)
那么首先我们可以对从s到t的路线划分为
从s到lca(s,t)
以及从t到lca
a.
from s to lca
要有贡献
易得dep[s]-dep[x]=valx
观察可得寻找s满足dep[s]=dep[x]+val[x]的数量
b.
from lca to t
要有贡献
易得dep[s]+dep[x]-dep[lca]-dep[lca]=valx
观察可得寻找s满足dep[s]-dep[lca]-dep[lca]=val[x]-dep[x]的数量
为了计算.我们规定lca被算在a部分中
2.实现
a.
不断从叶子到lca累加
易联想到差分
b.
由于种类不同可以开权值线段树
在递归回fa时合并线段树
3.问题
炸空间
4.解决
就权值线段树合并后空余节点进行一波垃圾回收
code
由于当前编译器有毒,我就不放代码了
QAQ