9.16上午补了一下暑假姚子奇讲的题，让姚子奇给我调个题他都不带鸟我的。P4180[BJWC2010]严格次小生成树先用kruskal将最小生成树求出来，之后再枚举不在最小生成树的每条边，设每条边的端点为x,y，如果加入这条边，则会形成一个环，于是我们考虑用这条边替换x和y路径上的一条边，但是由于是

语言题解本题其实没有什么好说的，主要是提供一种强大的，神秘的，诡异的，跑得飞快的，逆天的，唐诗的双\(\log\)做法首先考虑将答案分类，分成跨过这个语言的lca的和没跨过的对于没跨过的，可以发现就是对于每个点，求能扩展到的深度最低的节点，这个直接暴力做就是\(O(n)\)的，所以说我们直

虚树实际上是一颗浓缩子树；使用虚树的题目大部分具有查询的点有限，同时虚树构建的信息符合规则；做虚树的题目：步骤为先想出原树的暴力求解做法，然后构建虚树同时向其中添加有用信息（比如边权）；虚树的构建过程：虚树的构建大致有两种，但是两种方式都与dfs序有关；首先解释为什么与dfs序有

定义最近公共祖先（LowestCommonAncestor)，简称LCA，是算法竞赛中常用的、用以查找树上两个结点中，距离根结点最远的结点的算法。实现朴素算法过程每次找深度比较大的那个点，让它向上跳。显然在树上，这两个点最后一定会相遇，相遇的位置就是想要求的LCA。或者先向上调整深度较大的

0.前言最近公共祖先简称LCA（LowestCommonAncestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。这种算法应用很广泛，可以很容易解决树上最短路等问题。为了方便，我们记某点集\(S=\{v_1,v_2,\ldots,v_n\}\)的最近公共祖先为\(\text{LCA}(v_1,v_2,\ld

以下为自己口胡，未经网上搜索题解验证Statement一棵\(n\)个点的树，每条边有一个小写字母边权，\(m\)次询问，每次给定\(u,v,s\)，问字符串\(s\)在\(u\tov\)路径组成的字符串中出现了几次。\(n,m\le10^5,\sum|s|\le3\cdot10^5\).SolutionSol1把\(u\tov\)路径拆成\(u\t

P4649[IOI2007]training训练路径题意：原题地址给你一棵\(n\)个节点的树，上面还有\(m-(n-1)\)条非树边，每条非树边有一个代价\(c_i\)，要求你删掉若干条非树边使得之后的这棵树满足不存在任意一个长度为偶数的简单环。保证每个节点度数\(\le10\)。trick：如果树上不存在偶环

传送门：P3128[USACO15DEC]MaxFlowP首先要学会差分qwq题目意思：给定一个节点数为\(n\)的树，有\(m\)次操作。每次操作给你两个数\(s\)和\(t\)，你需要在\(s\)到\(t\)的路径所经过点的运输压力\(+1\)。求最后运输压力最大的点的压力。思路：发现\(s\)到\(t\)的路

首先，如果你做过BZ\(2144\)​，你可以发现一共只有：中间的往左跳。中间的往右跳。两边的往中间跳。第三个是对称的，我们不妨设他是\(fa\)，前两个一个\(ls\)，一个\(rs\)。那么我们有一棵二叉树，现在要问从一个点到另一个点方案数。两个点设为\(a,b\)。和\(2144\)不同的是，\(k

洛谷P3128[USACO15DEC]MaxFlowP题意给定一棵\(n\)个点的树，给定\(k\)个点对\((u,v)\)，把\(u\)到\(v\)路径上所有点的点权加一，最后求最大点权。思路树上差分模版。维护\(a_i\)表示每个点到根的加法标记。对于每个点对\((u,v)\)，把\(a_u\)，\(a_v\)加一，\(a_{LCA

洛谷P10931闇の連鎖题意给定一棵\(n\)个点的树，有\(m\)条附加边。第一次删除一条树边，第二次删除一条附加边。求有多少种方案使原来的树不联通。思路考虑求出\(f_i\)表示\(i\)的子树中有多少条附加边连向\(i\)的子树外。若\(f_i=0\)，则把\(i\)与\(i\)的父亲之间

初赛打得第\(3\)场。link。省流：\(6\)题，rk35，没过F，输麻了。过题顺序是A->D->B->C->E->G->(F)。F没调完。简要sol：A：过题时间：00:09:08，无罚时。难度：大概1500？二分答案一下，然后没了。复杂度\(\Theta(n\log{v})\)。B：过题时间：00:25:28，一发罚时。罚时原因：数组开小

MyBlogs[ARC183E]AscendantDescendant一个直接的想法是求出\(L_i,R_i\)表示极大的区间\([L_i,R_i]\)满足\(\forallj\in[L_i,R_i],b_j\in\text{subtree}(a_i)\)。由于树的性质，\([L_i,R_i]\)之间要么相离，要么包含。但是\(L_i,R_i\)并不是\(i\)能真正到达的点。因

题面如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。思路这次我们要使用的知识点是\(dfs\)和并查集，这个\(tarjan\)是离线的，我们要先把每个点的每一个要跟它求\(LCA\)的点给记录下来，接下来用\(dfs\)跑这么个流程：遍历这个点的每个子结点并进入子节点将子

RMQST表不用讲，浅显易懂，背背板子。例题Loj10121与众不同一个需要瞪眼发现单调性的题目。分析1.维护\(last_{val}\)表示元素\(val\)上一次出现的位置2.维护\(s_i\)表示以\(i\)为右端点的完美序列的起点，则：\[s_i=\max\left\{s_{i-1},last_{a_i}+1\ri

水紫。多次询问\(L,R\)，求出\(\sum\limits_{i=1}^n\min(d(i,L),d(i,R))\)。不失一般性的令\(del_L\ledel_R\)。分几部分考虑。\(L\)或\(R\)的子树中。预处理\(f_i\)代表\(i\)的子树中的点到\(i\)的距离和，\(s_i\)代表\(i\)的子树大小。转移方程：\(f_i=\su

CF2001E2由于对称，所以设\(heap[u]\)为两次确定堆，且第一次弹出的是\(u\)，\(heap[u,v]\)是第一次\(u\)，第二次\(v\)则答案就是\(\sumheap[u]=2^{n-1}·heap[x]\)其中\(x\)任意。不妨我们考虑第一次都是从第一个叶子弹出，那么对于其他不同的第二个弹出的点，根据对称性

之前学了一些算法，没有写算法总结，未来会陆续补一些。前置知识：树形\(dp\)，\(lca\)，\(dfs\)序。我们考虑\([HEOI2014]\)大工程这道题。显而易见，假如这道题只有一次询问，我们可以直接树形\(dp\)，快速求出答案，时间复杂度\(O(n)\)。但是，梦想是梦想，现实是现实，这题多组询问，假如一

tarjan之LCA学习笔记tarjan算法求LCA可谓是一个极其巧妙的离线算法其本质是利用DFS遍历时产生的DFS序和并查集来在线性的时间复杂度内求出所有询问的结果既然是离线算法，其和在线算法的区别就在与离线算法需要记录下所有查询，对查询进行一定操作来得到更高的效率，而这

次小生成树前置知识：图论最小生成树倍增求LCA概念次小生成树，分为严格次小生成树和非严格次小生成树。一下设图为\(G\)，最小生成树为\(T\)，非严格次小生成树为\(T'\)，严格次小生成树为\(T''\)。非严格次小生成树：在图\(G\)的所有除了\(T\)的生成树中，最小的那个。即\(

参考博客：最近公共祖先算法详解之最近公共祖先(LCA)瓶颈生成树Tarjan算法#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=5e5+10;usingi64=longlong;intn,m,s;vector<int>g[N];vector<pair<int,int>>q[N];boolst[N];intp[N

核心思路[USACO15DEC]MaxFlowP-洛谷sum[u]++,sum[v]++,sum[lca(u,v)]--,sum[fa[lca(u,v)]];本质上就是，对树进行差分自底向上进行统计处理#include<bits/stdc++.h>usingnamespacestd;intn,m;constintN=200000+10;vector<int>G[N];intdep[N],fa[N],hs

引入$\color{skyblue}P2495[SDOI2011]消耗战$题意给定一颗$n$个节点的树，每条边有边权。有$m$次询问，每次询问钦定$k$个特殊节点，问使得节点$1$不与任何特殊节点相连通所需要删除的最小总边权是多少。数据范围：对于\(100\%\)的数据，\(2\leqn\leq2.5\ti

虚树VirtualTree浓缩信息，把一整颗大树浓缩成一颗小树。下图中，红色结点是我们选择的关键点。红色和黑色结点都是虚树中的点。黑色的边是虚树中的边。OIWIKI两种建树方式1.第一种构造过程：二次排序+LCA连边(容易理解，常数略大)boolcmp(intx,inty){returndfn[x

关于虚树瞎扯某些树上问题，给了巨多节点，而实际上它们之中只有小部分能做出贡献，其余都是些水军，为杀尽OIers的脑细胞做出努力考虑重新种一棵树，浓缩信息，简化节点个数，于是产生了虚树。大概是长这个样子：红色结点是我们选择的关键点，即能够做出贡献的点。红色和黑色结点都是虚树中