23
2019
08

信息学奥赛一本通 树链剖分 1560:【例 1】树的统计

这题是模板题,先两个dfs把树剖开,重新编号,再借助线段树求解,求路径上的权值和还需要借助lca的思路先跳到同一条链上再利用区间求和。#include <iostream> #include <cstring> #include <cstdio> #define MIN -0x3f3f3f3f #define mem(a,b) memset((a),(b),sizeof((a)))