虚树给定一棵树，树上有一些关键点，你要建另一棵树，保留关键点，以及任意一对关键点的\(\text{LCA}\)。当你发现对于一棵树，你只有一些关键点有用的时候，就可以尝试建虚树。两次排序思路先把所有点按\(\text{dfn}\)序排序，然后把\(\text{dfn}\)相邻的两个点取出来，再把它们的\(\t

重温Tarjan,网上看了许多博客感觉都讲的不清楚.故传上来自己的笔记,希望帮到大家.提到的一些概念可以参考oiwiki,代码也是oiwiki的,因为我不认为我能写出比大佬更好的代码了.强连通分量:有向图的最大强连通子图(有向图中任意两点可达)Tarjan对每个结点

重温Tarjan,网上看了许多博客感觉都讲的不清楚.故传上来自己的笔记,希望帮到大家.提到的一些概念可以参考oiwiki,代码也是oiwiki的,因为我不认为我能写出比大佬更好的代码了.强连通分量:有向图的最大强连通子图(有向图中任意两点可达)Tarjan对每个结点维护

树链剖分怎么说呢，感觉只要不是求最大最小值好像都可以用树上查分代替。例题[ZJOI2008]树的统计-单点修改树链查询树链剖分板子，不多说了，代码注意细节就行。该用dfn的地方不要把点的编号传进去。#include<bits/stdc++.h>usingnamespacestd;#definels(id<<1)#define

轻重边把询问和修改都转到点上考虑。相当于给某些路径上的点都染上一种未出现过的颜色，然后查询某些路径上颜色相同的相邻点对数。注意初始时所有点的颜色应该互不相同树剖+线段树就做完了。需要特别注意的是树剖跳链时也会产生贡献。时间复杂度\(\mathcalO(n\log^2n)\)

树链剖分将整棵树可以铺到线性的去维护，于是利用线段树等可维护线性数组的数据结构，就可以做到很多事情了当然也包括省赛的J题--奇偶最小生成树，并且线段树还支持修改操作，这是ST表与普通倍增维护做不到的这是没有模数的代码：intn,m;llw[N];inthead[N],cnt;structE

        在图论中，割点与割边是图的重要性质，它们在图的连通性、网络流等问题中扮演着关键角色。在C++中，我们可以通过深度优先搜索（DFS）等算法来判定一个图中的割点与割边。        割点，又称关节点或桥接点，是指在无向连通图中，如果删除某个顶点后，图的连通分量数增

开始我最爱的tarjan吧。说一句，Tarjan最难的不是算法学习，而是如何使用。有向图的强连通分量有向图的强连通分量，是指在有向图的一块地方，在这块地方里面，每个点都能互相到达，这就叫做一个强连通分量定义这里是OIwiki上的定义强连通的定义是：有向图G强连通是指，G中任意两个结

abc167_dTeleporter#include<bits/stdc++.h>#defineptprintf(">>>")#definemid(((l)+(r))/2)usingnamespacestd;typedeflonglongll;typedeflongdoubleld;constllN=1e6+10,inf=1e18+10,mod=1e9+7;vector<ll>G[N];map&

前置定义有无向图\(G=(V,E).\)无向图的DFS树：从某一点\(root\)开始DFS，访问邻点\(.\)当搜索到点\(u\)时，我们遍历每一条以\(u\)为起点的边\((u,v_i)\)，且定义有向边\(u\longrightarrowv_i.\)于是DFS的过程全部完成之后，所有被定义的有向边就会组成一颗以\(r

首先是两篇模板割边点击查看代码inthead[N],cnt=1;structEdge{intfrom,to,nxt;}e[N<<1];voidadd(intu,intv){e[++cnt].from=u;e[cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}intdfn[N],back[N],tim,bri_cnt;//dfn

首先是两篇的代码割点点击查看代码inthead[N],cnt=0;structEdge{intfrom,to,nxt;}e[N<<1];voidadd(intu,intv){e[++cnt].from=u;e[cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}intdfn[N],back[N],tim;//dfn[i]时

前情提要，我主要看的是这位大佬的讲解，用的是谷的代码，所以会有点奇怪大概就是这么个意思dfs1用来处理树的dfs序，处理出重链大小和对应的重儿子voiddfs1(intnow){ son[now]=-1; siz[now]=1; for(inti=head[now];i;i=edge[i].from){ intto=edge[i].to; if(dep[to])c

树链剖分把一棵树剖分成若干条链，然后对链进行操作，维护路径上的信息。有点像分块，也是暴力做法，单个操作太慢就整个操作。我们一般用重链剖分，也就是根据子树大小把边分成轻重边。重链剖分定义重儿子：所有子节点中子树最大的节点，多个一样的取任意。轻儿子：不是重儿子的就是轻儿

RingRoad2题目链接思路：先考虑什么情况下会相交，对于两条道路\((x_1,y_1)\)和\((x_2,y_2)\)。这里默认\(x<y\)，显然当$x2<x1<y2$并且\(y1<x2\)||\(y1>y2\)时(\(x1\)和\(y1\)互换也可以，即一个点在范围内，一个点在范围外)，那么两条道路就会产生交点。因此对于

P3007[USACO11JAN]TheContinentalCowngressG题目链接思路：2-SAT模板，经典的或条件，那么直接建图即可，对于可行解，我们直接枚举每个方案支持和反对，然后染色判断即可。代码：#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_

CatowiceCity题目链接思路：第\(i\)个人认识第\(j\)只猫，所以选了第\(i\)个人就必须选第\(j\)个人，那么我们连一条\(i\)指向\(j\)的边。那么同一个连通分量中就必须同时选择。考虑不能对其他猫产生影响，我们可以选择一个没有出边的强连通分量全部选人(即编号为1的强

P5782[POI2001]和平委员会题目链接思路：因为\(u\)和\(v\)矛盾，即\(\lnot(u\landv)\)。转化成\(\lnotu\lor\lnotv\)。那么根据\(2-SAT\)标准处理方式。转化为：\((u\rightarrow\lnotv)\land(v\rightarrow\lnotu)\)。这里有个小技巧：我们将下标-1，这样我

2-SAT2-SAT，简单的说就是给出\(n\)个集合，每个集合有两个元素，已知若干个\(<a,b>\)，表示\(a\)与\(b\)矛盾（其中\(a\)与\(b\)属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选\(n\)个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。对

P4171[JSOI2010]满汉全席2-SAT题目链接思路：2-SAT模板题，我们将满席定为1，汉席定为0.那么建边即可。判断同一道菜满汉是否在强联通分量中即可。注意多测清空！！！代码：vector<int>e[N];stack<int>stk;intdfn[N],low[N],tot;intinstk[N],scc[N],siz[N],cnt;intn,m;void

由题述，\(X\)满匹配，根据Hall定理，有对于任意一个有\(k\)个妹子的集合，她们能配对的男生的人数\(\gek\)。把每个妹子看作她所连接的两个（可能是同一个）男生间的无向边，则每个连通块必然是树或基环树。问题转化为给每条无向边定向，满足每个点的入度不超过\(1\)，求最大边权和。对

求DAG中一条最大点权链用scc缩点完成后其实问题就回到了DAG，这样一个问题，开始dfs写多了，直接找入度为0为起点一个dfs，结果就搜爆了。正解：寻找DAG中一个拓扑排序，按照拓扑序遍历点，再遍历点的边，dp维护答案而Tarjan缩点完成后新点的倒序（ans_scc->1）就是一个拓扑序,于

考虑到因为只有\(3\)行，所以第\(2\)行为\(1\)的条件就是\(1\)的个数\(\ge2\)。对于这种只能去正负且有无解的问题，可以想到用个\(\text{2-SAT}\)。于是接下来考虑用\(\operatorname{AND},\operatorname{OR},\operatorname{XOR}\)来表示至少有\(2\)个\(1\)。考

这是摘自算法书上的一篇Tarjan求割点算法dfn[i]代表时间戳数组back[i]代表该点不依靠祖先节点能回到的最远的祖先节点采用链式前向星建图，结果存储在iscut[]数组中点击查看代码inthead[N],cnt=0;structEdge{intfrom,to,nxt;}e[N<<1];voidadd(

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