几乎同「『LNOI2014』LCA」……
只不过套了个 k 次方。
原来点 p 的贡献是 1,即 depp−depfap。
其中 depp 表示 p 的深度,fap 表示 p 的父亲。
现在,我们考虑把每个点到根路径上的深度 k 次方像上面这样差分。
即令点 p 的贡献为 depkp−depkfap。
然后在线段树上同时维护这个附加权值即可。
代码:
1 |
|
几乎同「『LNOI2014』LCA」……
只不过套了个 k 次方。
原来点 p 的贡献是 1,即 depp−depfap。
其中 depp 表示 p 的深度,fap 表示 p 的父亲。
现在,我们考虑把每个点到根路径上的深度 k 次方像上面这样差分。
即令点 p 的贡献为 depkp−depkfap。
然后在线段树上同时维护这个附加权值即可。
代码:
1 | #include <cstdio> |
Related Issues not found
Please contact @Alpha1022 to initialize the comment