bzoj 2152 聪聪可可
题目大意：
求树上边权和为3的倍数的路径的条数
思路：
点分治练习题
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
但是树形dp明显更加优秀
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
luogu 3806 【模板】 点分治1
题目大意：
树上Q次询问 每次询问路径长度为k的路径是否存在
思路：
为什么那么多$n^2$合并的代码啊喂
由于询问数较小 跑Q次点分治即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
bzoj 3672 购票
题目大意：
每个点$x$可以购买一个车票到距离不超过$lim_x$的祖先，车票价格为$p_x*(dis_{x,ancestor})+q_x$
求每个点到树的根的最小代价
思路：
首先想到了线段树分治的$log^3n$的优秀做法 然后学了一波点分治做法
很明显可以想到斜率优化 考虑如何处理距离限制
在点分治的过程中，把分治重心子树内的所有按照$dis_i-lim_i$排序，这样就可以依次由下至上加入最高点$x$-$root$的路径上的点
这样可以保证所有时刻的凸包都是满足要求的
每次分治的时候先处理树中不算分治重心儿子的部分 然后处理分治重心的儿子即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
bzoj 4012 开店
题目大意：
一棵树，每个点有一个权值，有边权，Q次询问
每次询问给$u,L,R$ 求$\sum_{val_i \in [L,R]} dis_(u,i)$
思路：
1. 由于$[L,R]$可以转化为$[0,R]-[0,L-1]$ 考虑使用主席树
题中所求可以转化为$\sum _{val_i \in [L,R]} dis_u+dis_i-2*dis_{lca}$ 前两项很容易计算
计算$\sum_{i \in State} dis_{lca(x,i)}$时候，可以树剖+线段树把所有集合内的点$i$到根的路径上的点+1
线段树上每个点点权为该点连向父亲的边的边权 因为是主席树所以需要标记永久化
然后每次查询的时候查一下主席树上该点到根的路径上的权值和
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
2.依然是差分 建立点分树
则答案可以沿着点分树暴力想上从$node_{start}$开始跳，分别统计每个点为$lca$的距离
在构建点分树的时候顺便统计该点分树子树内所有点到这个点的距离之和以及到这个点的父亲的距离之和
则每个点的答案为$\sum_{val_i \in [L,R]} (\sum dis(x,i)-\sum dis(fa_x,i)) + cnt \times (dis(x,node_{start}-dis(fa_x,node_{start}))$
为了方便使用$vector$
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
bzoj 4016 最短路径树问题
题目大意：
求出一个图的最短路径树，要求从1开始的字典序最小，求在树上点数为k的路径中最长的路径长度以及有多少个最长路径
思路：
求出一个最短路径树且字典序最小，可以先用$dij$求出最短路径图，在这个图上每个点的儿子按照字典序排序，$dfs$即可求出要求的树
之后就是点分治裸题了，顺便维护一下数量即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
bzoj 1758 重建计划
题目大意：
求路径上边数在$[L,R]$中，边权平均值最大的路径
思路：
这种平均值的东西首先肯定要二分一下平均值
考虑合并，对于每个新的子树，记录一下每个深度的最长路径
这样的话每个深度$i$可以由$[L-i,R-i]$这个区间的路径转移过来
维护一个单调队列即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include
bzoj 1095 捉迷藏
题目大意：
一棵树，每个点有黑白两个颜色 支持单点修改改颜色与查询最远两个黑点的距离
思路：
建立点分树，对于每个点开两个堆，分别维护点分树子树内所有点到分治树上$fa$的距离以及分治树上儿子的第一个堆的堆顶
再维护一个全局堆维护每个点第二个堆的堆顶
这样全局暴力，每次修改改一个链即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include