题目链接 https://blog.bill.moe/long-chain-subdivision-notes/ http://www.cnblogs.com/zzqsblog/p/6700133.html 长链剖分模板. 6,7,8,20个点RE,没什么办法了..(迷) #include <cstdio> #include <cctype> #include <vector> #include <algorithm> #define gc() getcha

给出一棵树求K级祖先.O(N*logN+Q) 更详细的讲解见:https://www.cnblogs.com/cjyyb/p/9479258.html /* 要求k级祖先,我们可以把k拆成"2^highbit(x)+tmp 形式 (highbit(x)为x在二进制位下的最高位),然后用倍增的方法把highbit(x)的部分跳了 剩下tmp的同样可以预处理掉,这样预处理就是O(n*logn)的效率, 所以对于每个询问就是O(1)回答,这样的效率就是O(n*logn+q). 于是就考虑用长链剖分.

  2020/4/30   15:55 树链剖分是一种十分实用的树的方法,用来处理LCA等祖先问题,以及对一棵树上的节点进行批量修改.权值和查询等有奇效. So, what is 树链剖分? 可以简单的理解为,将一棵树分成许多条不相交的链,每次我们只要得知链首,便可对该条链上所有的点用数据结构(like 线段树)进行相关操作 . 首先,介绍最常用的轻重链剖分. 明确最常用的轻重链概念: 重儿子:父亲节点的所有儿子中子树结点数目最多(size最大)的结点: 轻儿子:父亲节点中除了重儿子以外的儿子:

题目描述 输入 第一行包含一个正整数N,表示X国的城市个数. 第二行包含两个正整数L和U,表示政策要求的第一期重建方案中修建道路数的上下限 接下来的N-1行描述重建小组的原有方案,每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号 输出 输出最大平均估值,保留三位小数 样例输入 4 2 3 1 2 1 1 3 2 1 4 3 样例输出 2.500 提示 N<=100000,1<=L<=U<=N-1,Vi<=1000000 这题算

https://vijos.org/d/Bashu_OIers/p/5a79a3e1d3d8a103be7e2b81 求k级祖先,预处理nlogn,查询o1 //#pragma GCC optimize(2) //#pragma GCC optimize(3) //#pragma GCC optimize(4) //#pragma GCC optimize("unroll-loops") //#pragma comment(linker, "/stack:200000000&

2450. 距离 ★★   输入文件:distance.in   输出文件:distance.out   简单对比时间限制:1 s   内存限制:256 MB [题目描述] 在一个村子里有N个房子,一些双向的路连接着他们.人们总喜欢问这个“如果1想从房子A走到房子B有多远?”这个通常很难回答.但幸运的是在这个村里答案总是唯一的,自从道路修建以来这只有唯一的一条路(意思是你不能去一个地方两次)在每两座房子之间.你的工作是回答所有好奇的人. [输入格式] 输入文件第一行有两个数n(2≤n≤10000

题意 给你一颗有 \(n\) 个点并且以 \(1\) 为根的树.共有 \(q\) 次询问,每次询问两个参数 \(p, k\) .询问有多少对点 \((p, a, b)\) 满足 \(p,a,b\) 为三个不同的点,\(p, a\) 都为 \(b\) 的祖先,且 \(p\) 到 \(a\) 的距离不能超过 \(k\) . \(n\le 300000 , q\le 300000\) 不要求强制在线. 题解 令 \(dep[u]\) 为点 \(u\) 的深度,\(sz[u]\) 为 \(u\) 的子树

题目描述 给定一棵n个点的树,树上每条边的长度都为1,第i个点的权值为a[i].Byteasar想要走遍这整棵树,他会按照某个1到n的全排列b走n-1次,第i次他会从b[i]点走到b[i+1]点,并且这一次的步伐大小为c[i].对于一次行走,假设起点为x,终点为y,步伐为k,那么Byteasar会从x开始,每步往前走k步,如果最后不足k步就能到达y,那么他会一步走到y.请帮助Byteasar统计出每一次行走时经过的所有点的权值和. 输入 第一行包含一个正整数n(2<=n<=50000).表示节

传送门 长链剖分模板题. 题意简述:允许O(nlogn)O(nlog_n)O(nlogn​)预处理,让你支持O(1)O(1)O(1)查找任意一个点的kkk级祖先. 思路:因为要O(1)O(1)O(1)求,因此需要用到长链剖分的一些性质. 所谓长链剖分是类比重链剖分的一种划分树的方式,我们考虑将整棵树用若干条极长链拼接起来就是长链剖分. 那么它有如下几个几个性质: 所有长链的长度之和为O(n)O(n)O(n) 一个节点的kkk级祖先所在的长链的长度至少为kkk 可以根据长链剖分的定义想 然后这题就

首先,重链剖分我们有所认识,在dsu on tree和数据结构维护链时我们都用过他的性质. 在这里,我们要介绍一种新的剖分方式,我们求出这个点到子树中的最长链长,这个链长最终从哪个儿子更新而来,那个儿子就是所谓的“重儿子”,也可以叫长儿子. 我们的做法就是,在统计一个点的信息时,对于重儿子,我们直O(1)接继承它的答案(这里有指针技巧,只能看代码,不可言传),对于轻儿子我们暴力统计. 复杂度分析:一个点被计算,最多只会在作为重链上的点时被继承一次,在重链顶端时被暴力统计一次.所以最终复杂度是O(

BZOJ 洛谷 \(Description\) 给定一棵树,每次询问给定\(p,k\),求满足\(p,a\)都是\(b\)的祖先,且\(p,a\)距离不超过\(k\)的三元组\(p,a,b\)个数. \(n,q\leq3\times10^5\). \(Solution\) \(p,a,b\)都在一条链上. 那么如果\(a\)是\(p\)的祖先,答案就是\(\min(dep[p],\ k)*(sz[p]-1)\).可以\(O(1)\)计算. 如果\(a\)在\(p\)的子树中,答案就是\(\sum

传送门 长链剖分优化dpdpdp水题. 题意简述:给一棵树,mmm次询问,每次给一个点aaa和一个值kkk,询问满足如下条件的三元组(a,b,c)(a,b,c)(a,b,c)的个数. a,b是c的祖先 a,b的距离不超过k 思路: 考虑单独处理每一个询问怎么做. 显然a,ba,ba,b的位置关系有两种. bbb是aaa的祖先,此时ccc一定在aaa子树中,这种情况的三元组个数是(sizea−1)∗min(k,depa−1)(size_a-1)*min(k,dep_a-1)(sizea​−1)∗m

[CF860E]Arkady and a Nobody-men 题意:给你一棵n个点的有根树.如果b是a的祖先,定义$r(a,b)$为b的子树中深度小于等于a的深度的点的个数(包括a).定义$z(a)=\sum\limits r(a,b)$(b是a的祖先).要你求出每个点的z值. $n\le 5\times 10^5$ 题解:一开始naive的思路:将所有点按深度排序,将深度相同的点统一处理,统计答案时相当于链加,链求和,用树剖+树状数组搞一搞,时间复杂度$O(n\log^2n)$. 后来看题解

题意 题目链接 Sol 长链剖分 又是一个用各种花式技巧优化的暴力 它的主要思想是:对于每个节点,把深度最深的子节点当做重儿子,它们之间的边当做重边 这样就会有一些非常好的轻质 所有链长总和是\(O(n)\)级别的 任意一个点的\(k\)级祖先的子树深度\(\geqslant k\) 首先我们维护出每一个重链头向上\(len[i]\)个节点是什么,沿着重链走向下\(len[i]\)个节点是什么 \(len[i]\)表示该节点所在重链的长度 同时预处理出找祖先的倍增数组 每次询问的时候,首先找到\

传送门 长链剖分的板子(又是乱搞优化暴力) 对于每一个点,我们定义它深度最深的子节点为它的重儿子(为什么不叫长儿子……),他们之间的连边为重边 然后长链剖分有几个性质 1.总链长为$O(n)$ 2.一个节点的$k$级祖先的子树深度必定大于等于当前节点的子树深度 以上两点稍微yy一下就能发现是对的 然后回到这道题.我们设$len[u]$为这一条长链的长度,对于每一个长链的顶点,我们维护它的1到$len[u]$级儿子以及1到$len[u]$级祖先 同时预处理找祖先的倍增数组,并预处理出1到$n$的每

题面 一棵以 1 1 1 为根的 N N N 个节点的有根树, Q Q Q 次询问,每次问一个点 u u u 的 k k k 级兄弟有多少个(第 k k k 代祖先的第 k k k 代孩子),如果没有则输出 0 . N , Q ≤ 1 0 6 N,Q\leq 10^6 N,Q≤106 . 题解 像这种一个 log 可过的题目就是拿来 O(n) 做的 狗狗有言:挺板的长链剖分. 我们用离线+长链剖分来解决第 k k k 代孩子的问题,每个链顶存一个数组,表示每一代孩子的个数,把轻儿子的链合并.这个

传送门 官方题解其实讲的挺清楚了,就是锅有点多-- 一些有启发性的部分分 L=N 一个经典(反正我是不会)的容斥:最后的答案=对于每个点能够以它作为集合点的方案数-对于每条边能够以其两个端点作为集合点的方案数.原因是:对于每一种合法方案,集合点一定是树上的一个连通块,满足\(n=m+1\).算点时,这种方案被算了\(n\)次:算边时,这种方案被算了\(m=n-1\)次,所以每一个方案都恰好被算了一次. 有\(DP\):设\(f_i-1\)表示选择了包含\(i\)和\(i\)的子树中的点的一个连通

题面 给定一棵树,每次询问一个点的\(k\)次祖先,强制在线. Vijos 题解 长链剖分. 链接暂时咕咕咕了. 现在可以戳链接看题解了 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std

[BZOJ3653]谈笑风生(长链剖分) 题面 BZOJ 洛谷 权限题啊.... 题解 首先根据题目给的条件,发现\(a,b\)都要是\(c\)的父亲. 所以这三个点是树上的一条深度单增的链. 因为\(a,b\)之间距离不超过\(k\),并且\(a\)被钦定了,所以只有两种情况: 一种是\(a\)是\(b\)的祖先,贡献是\(\sum_b size[b]-1\),也就是所有\(b\)可以选择的点的子树和. 另外一种\(b\)是\(a\)的祖先,贡献是\(\sum_b size[a]-1\),钦定

[COGS2652]秘术「天文密葬法」(长链剖分,分数规划) 题面 Cogs 上面废话真多,建议直接拉到最下面看一句话题意吧: 给个树,第i个点有两个权值ai和bi,现在求一条长度为m的路径,使得Σai/Σbi最小 题解 看到这个式子就是裸的分数规划吧... 二分一个答案\(k\),式子变成了找一条长度为\(m\)的路径(题目里面路径长度的定义是点数) 满足\(\sum a-k\sum b\le 0\). 首先直接把\(m=-1\)也就是没有限制的点直接判掉,这个东西没有任何意义. (其实\(m