题解(下文子树权值是指当前点到重心节点路径的最小值) 摁….卡线段树….选择树状数组吧(树状数组下标是权值 维护前缀区间路径长度的最大值) 因为是点对问题….点分治没跑了 我们考虑子树合并 对于大于当前结点权值的点 我们可以在$O(logn)$的情况下得到答案 但是对于小于当前权值的点我们没有比较高 ...

题解这题确实妙妙秒啊!!!!! 首先这是一个点对问题 我们还是从点分入手 仍然考虑子树点对 我们发现对于当前子树 能与其组成点对的是同一个重心的情况下之前的子树 考虑到类似dfs序的东西 我们称之为点分序吧 所以我们能把这个树形问题转化为序列问题 因为点分的性质保证每个点最多出现$logn$次 ...

题解:强行凑题….. 前面构造最短路树 然后后半部分模板点分统计贡献 这个最短路树要保证路径的字典序最小 那么我们可以跑出最短路 枚举边 看距离差值是否等于边权 然后连边 对于所有连边排序以后 做$dfs$建树 第二部分就直接考虑子树合并 维护每个深度下的最大距离 以及方案数 枚举统计贡献 复杂度 ...

题解:这题稍微有点绕 如果我们仅仅只要查询一段路径的上$0/1$路径段的数量相等的话 直接做点分就行了 但是现在需要存在一个中间转折点 要这个点到两段的$0/1$路径的数量段同样相等 所以我们考虑每个点到重心节点的$0/1$数量段的差值 我们根据节点之前的祖先节点是否出现和其一样差值的节点将其 ...

题解第一眼以为$q$很大…想了一晚上…. 然后早上起来看题….$q<=100$ 惊了 好了 言归正传 $q<=100$那就直接暴力跑100次点分$ check $ 据说这样会被卡常数???反正我没试过 我们考虑 直接在重心分治的时候$check$ 每次把新的子树合并上去 然后$q$次$ ...

题解讲个鬼故事~~ 第一次xjb写了一个点分治 统计贡献甚至没有去掉同颗子树的情况 骗了75分……..然后对拍写挂了 生成数据从1到n 对拍找不到错 …真是太菜了 言归正传: 对于统计贡献 我们可以把重心的儿子的子树一个个合并 然后维护答案就行了 坑点就是….别把$K$当做$N$ 然后注意别用 ...

题解

点分治模板题

不同的是 我们不需要sort 也不需要去重

对于每个子树重心做一个树$dp$即可 $dp[x][y]$表示x的子树中到x距离模3后y的个数

然后对于每个子树重心 合并维护答案即可

$复杂度O(nlogn)$

题解

同上题

题解点分治模板题 第一次写点分治 那就把我的心酸证明历程也记录下吧 首先:前置知识点 树的重心(当$x$为根时,其子树节点的$size$的最大值最小) 然后每次以子树重心分治 保证分治层数不超过$logn$层 证明: 我们假如其$size_u>size/2$那么 我们必然可以往其$siz ...

题解首先路径的选择应该是直径的某一段区间…证明略(虽然我也是直观感受的) 然后我们考虑对直径上区间的选择 对于区间[l,r]的价值为$max(dis(直径左端点,l),max(dis(直径右端点,r),子区间上的价值))$ 当$l$保持不变,$r$增加时,区间价值单调不增加,所以我们应该对于每个左 ...