这道题比较有意思。
题目中贡献最多影响到距离一个节点为\(\log\)的节点。
题目要修改深度相同且在某个子树的节点。可以考虑bfs序+线段树。
对一段深度相同且在某个子树的节点，他们在bfs序上是连续的，可以修改。
考虑从一个节点\(x\)向上跳修改。
先把子树的所有距离\(x\)不超过1且在子树的节点的值\(-=w\),把\(y\)的子树内距离\(y\)不超过\(2\)且在子树的节点的值\(-=w/2\)....
再设一个值\(y=fa_x\)。把\(y\)的子树内距离\(y\)不超过\(1\)且在子树的节点的值\(-=w/2\),把y的子树内距离y不超过2且在子树的节点的值\(-=w/4\)....
但是这里算重了，要把\(x\)子树的距离\(x\)不超过1且在子树的节点的值\(+=w/4\),把y的子树内距离y不超过2且在子树的节点的值\(-=w/8\)....
这可以使用线段树简单实现。
在统计答案时，维护区间\(\min\)值，暴力递归\(\min<0\)的部分。这些点破产了。
使用树状数组+dfs序统计某个点子树的破产点的个数，即可回答询问。
这里的复杂度是\(\min<0\)的节点形成的虚树大小。最坏情况是节点数\(*\log_2n\)。不是瓶颈。
所以我们可以在\(\log_2^2V*\log_2n\)的时间复杂度求出了答案。
然而有更加优秀的做法。
我们的线段树可以解决对一段连续节点的区间+和区间查询。
但是我们的问题更弱，只需要单点查询，对子树距离\(d\)的点修改即可。
考虑每个点对另外的点的贡献。设\(f_{i,j}\)表示\(i\)节点对子树距离为\(j\)的点的贡献。
考虑上面使用线段树修改的过程。
我们需要对一个节点\(x\)距离\(=k\)的点\(-=va\)，则在数组上\(f_{x,k}-=va\)。
但是有些贡献算重了，要加回去。也可以在\(f\)上简单更新。
查询一个点\(x\)就是跳它的祖先\(z\)，设\(dis(x,z)=t\)，则答案\(+=f_{z,t}\)
这样子，修改时间复杂度降低到\(\log_2^2n\)。
整体二分。
有一种新的整体二分。
把所有询问一起二分。处理出所有的询问的终点值\(md\)。
把\(md\)排序，从小到大处理\(md\)。
使用vector。\(g_{x,i}\)是一个二元组表。\(g_{x,i,po,0/1}\)表示\(x\)距离\(i\)的点在\(g_{x,i,po,0}\)时间后，\(g_{x,i,po+1,0}\)时间前的值是\(g_{x,i,po,1}\)
可以简单使用前缀和处理。
整体二分时候按照\(md\)排序后扫描线。
时间复杂度\(n\log_2^2V\)
原文：https://www.cnblogs.com/ctmlpfs/p/13677219.html