20240703DSroundT1考虑区间子区间问题直接扫描线加历史版本和，考虑修改。现在扫到\(r\)，线段树每个位置\(i\)维护的是\(i\)到\(r\)的区间\(lca\)，这些\(lca\)的深度具有单调性，考虑直接二分一下位置，然后\(r\)扫到\(r+1\)时，深度大于\(lca(r,r+1)\)的\(

前言想象我在口胡三样我都不熟悉的东西并尝试称之为“学习笔记”。其实不过是我自己对于它的一点小理解，甚至可能是错误的！无所谓，口胡！口胡！口胡！口胡！口胡！一些备注\(dfn_u\)为点\(u\)的dfn序，\(nfd_i\)表示第\(i\)个dfs到的点是啥（前者的反数组）dfs序求lca这个很简单，想

数据结构专题.CF1192B动态修改边权,查询树直径.方法1:首先考虑常规的树上问题,即树剖一类方法不便于处理和合并直径这一类信息,于是考虑拍成序列做(树莫队就是这种想法).考虑任一条路径是由左右端点和LCA连成,因此考虑可以用于求LCA的欧拉序列,刚好可以用差分法把任意一条路

行列式基础概念\(n\)阶行列式\[\begin{vmatrix}a_{11}&a_{12}&...&a_{1n}\\a_{21}&a_{22}&...&a_{2n}\\...&...&&...\\a_{n1}&a_{n2}&...&a_{nn}\\\end{vmatrix}\]完全展开式$\sum_{

P3398仓鼠找sugar题意简述给定一个\(N\)个节点的树形结构。接下来有\(q\)次询问，每次询问给定\(4\)个节点\(a,b,c,d\)，请计算\(a\)到\(b\)的简单路径和\(c\)到\(d\)的简单路径是否有相交的节点。对于每个询问，输出Y/N表示答案。解题思路&Code通过手玩样例可以发现，\(a\simb\)

题意简述给定一个\(N\)个节点的树，接下来有\(q\)次询问。每次询问给定\(a,b,c\)，请问存在多少个节点\(i\)，使得这棵树在以\(i\)为根的情况下，\(a\)和\(b\)的LCA是\(c\)。解题思路首先通过分析样例，我们发现：\(a,b\)的LCA一定在它们之间的简单路径上，所以如果\(c\)不在\(a,b\)之间的简

挺有意思的题。思路考虑一个比较自然的做法。我们每次对于一棵树，我们将它的某一条链抽出来。这样，我们只需要知道这颗树的所有节点与链底的\(\text{lca}\)，就可以知道它是属于这条链上哪一个节点的下面。然后就可以递归处理。由于交互库不是自适应的。我们可能可以想到随机

公共祖先：在一棵有根树上，若节点\(F\)是节点\(x\)的祖先，也是节点\(y\)的祖先，那么称\(F\)是\(x\)和\(y\)的公共祖先。最近公共祖先（LCA）：在\(x\)和\(y\)的所有公共祖先中，深度最大的称为最近公共祖先，记为\(LCA(x,y)\)。LCA显然有以下性质。在所有公共祖先中，\(LC

结论树上一个点\(x\)到路径\(u\rightarrowv\)的最短距离为：\[dep[x]+dep[\operatorname{lca}(u,v)]-dep[\operatorname{lca}(x,u)]-dep[\operatorname{lca}(x,v)]\]其中，\(dep\)为该点的深度，\(\operatorname{lca}\)为两点的最近公共祖先。证明我们提取出同时包含\(x,u,

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;#define_for(i,a,b)for(registerint(i)=(a);(i)<=(b);(i)++)#defineFor(i,a,b)for(registerint(i)=(a);(i)>=(b);(i)--)#defineINF0x7fffffff

如果我来到了我们的LCA，我是不是就可以假装偶遇你了首先是倍增法，和ST表如出一辙呢。注意N通常在5e5的范围点击查看代码inthead[N],cnt;structEdge{intfrom,to,nxt;}e[N<<1];voidadd(intu,intv){e[++cnt].from=u;e[cnt].to=v;

原题链接题解由易到难，先不考虑交替的事情，既然要尽量少的涂色，那么我最少要涂几条颜色的边？（由于图不一定联通，这里先考虑连通图的情况）如果一条边处于一个环内，那么这个边就可以不涂色。所以只要有环我就可以选择一条边不涂色，那么到最后，涂色的边构成一棵树接下来考虑这颗树能否实现

LCA就是最近公共祖先，表示为\(\operatorname{lca}(a,b)\)，它的求解方法主要有两种。倍增法这是最常用的一种可以动态求LCA的算法。时间复杂度为\(O(\log{n})\)。中心思想这个算法中有两个特殊的数组：\(depth[i]\)和\(fa[i][k]\)。\(depth[i]\)：\(i\)点的深度，以\(root\)

#include<bits/stdc++.h>#defineintlonglong#defineMAXN500010usingnamespacestd;structedge{intnxt,to;};edgee[MAXN*2];inth[MAXN],ei;voidadd(intx,inty){ei++;e[ei].to=y;e[ei].nxt=h[x];h[x]=ei;}intu[

题目大意给出一个\(n\)个节点的有根树。设\(dep[i]\)表示点\(i\)的深度，\(\operatorname{LCA}(i,j)\)表示\(i\)与\(j\)的最近公共祖先。有\(m\)次询问，每次询问给出\(l,r,z\)，求\(\sum_{i=l}^rdep[\operatorname{LCA}(i,z)]\)。\(1\len,m\le50000\)。思

倍增大专题[AHOI2008]紧急集合/聚会-洛谷题意：给定一棵树，多次查询费马点（bushi费马点的含义是：到三个点的距离之和最小Solution:考虑画图发现树上三点两两求lca，必然至少两个相同，然后我们只需要让费马点为另一个点就可以了，因为这一段路程只需要一个点走就最好了。//考虑到让

联合权值显然可以枚举中间点，然后做完了。CodeCowPoliticsG显然的，对于每种颜色，点对中一定包含深度最大的点。枚举另外一个点即可。CodePassablePaths显然我们需要选择深度最深的点和距离该点最远的点，判断其他点是否在它们的路径上即可。CodeAHOI2008聚会由题意可得

LCA可以将一条树上路径拆成一或两半，所以我们可以将很多关于区间的算法拓展到树上。仓鼠找suger洛谷P3398考虑两条相交的纵向路径\([A,B]\)和\([C,D]\)，如图：如果两条路径相交那么\(C\)是\(B\)的祖先，\(A\)是\(D\)的祖先，对于任意的路径\([A,X,B]\)和\([C,Y,D]\)，如

对dfn序开数据结构（如线段树），每个结点\(p\)维护对应dfn序区间内所有存在的点所构成的虚树大小\(sz_p\)，需要维护区间内所有存在的点中dfn序最大点\(rv_p\)和最小点\(lv_p\)、区间内所有存在点的LCA\(lca_p\).考虑合并左右儿子\(ls,rs\)，按两棵虚树是否相交分讨，先考虑

有人说，直接点分树，力大砖飞，非常不错！实际上这种做法非常的垃圾，很多时候我们使用点分树，一定是不得不使用点分树，比如模板题，强制在线，非常的恶心，所以我们使用点分树。而点分树是否必要呢？既然你能看到这篇blog，他肯定是不必要的！我们今天来发掘dsuontree的美妙性质，让他求解这个问题！然

树链剖分&树上差分有一些相关的树上操作主要是写可持久化的时候的时候发现\(lxl~Day~5\)中有些东西根本不是可持久化...树链剖分主要记录重链剖分，不讲基本原理，只是题解CF536ETavasonthePath好像并没有可持久化，但是树剖先考虑在序列上做这个问题，

染色给定一棵\(n\)个节点的无根树，共有\(m\)个操作，操作分为两种：将节点\(a\)到节点\(b\)的路径上的所有点（包括\(a\)和\(b\)）都染成颜色\(c\)。询问节点\(a\)到节点\(b\)的路径上的颜色段数量。颜色段的定义是极长的连续相同颜色被认为是一段。例如112221由

题目描述输入一张无向图，对于无向图的每条边u,v,w，将u和v转换成二进制后，u是v的前缀。给出q次询问，每次输入s，t，求s到t的最短距离。题解从题目数据而言，n为1e5，m为2e5，显然一般的多源最短路算法无法完成。考虑此题的特殊性质：由于边仅可能从u连向以u为前缀的v，那么若建立一颗以1为根的完

点分治对于一棵子树，即正常dfs的根改成该子树重心，递归下去是按原树儿子所在子树的重心（每次找一遍），变成了子问题，可以处理与树形态没什么关联的问题发现siz每次减半，故深度log层；同时siz大小总和的复杂度是对的由于总是处理的整棵子树，而答案与子树遍历关系无关，所以一定是对的

如果你既会倍增，又会并查集，那你一定会倍增并查集吧！link数据范围明示\(O(n^2)\)无法通过。众所周知，倍增是\(O(\logn)\)的，并查集近似\(O(n)\)的，它们结合一下不就能过了吗？先来重新考虑一下倍增的本质。倍增倍增最经典的用法是ST表。我们将一个区间拆成两个长为\(2^k\)