A.Min-FundPrison(Medium)考虑一个边双连通分量一定不可能分为合法的两部分，于是进行缩点。缩完后显然是一个森林。设\(dp_{i,j,0/1}\)表示第一堆有\(i\)个点，第二堆有\(j\)个点，两堆点有没有用一条边连起来的最小花费。对于每棵树，考虑将它加入第一堆/加入第二堆/一部分加

P1486[NOI2004]郁闷的出纳员题目翻译：维护一个可重数集，共有\(n\)次操作，和一个最小限制\(min\)，共有四种操作：\(I\)\(k\)给集合添加\(k\)若\(k<min\)则直接删除（不算入删除个数）\(A\)\(k\)将集合中的所有元素加上\(k\)\(S\)\(k\)将所有元素减少\(k\)并将所有值

P2234[HNOI2002]营业额统计题目翻译：给定\(n\)个数，每一个数都要统计其最小波动值，波动值的定义是当天银收额和之前某次的营收额的差的绝对值，而要求每一天最小波动值的和（第一天波动值为当天营收额）思路：分析题目可以发现，最小波动值就是当天营收额与之前小于它的最大营收额的差

1.Seqkit提取seqkit作为一个非常全能的软件，之前有多次利用到，本来早就该学习了，却一直拖欠了下来。这次要进行一个cds序列的提取，所以在此做一个记录。目标：将含有多个转录本的Pep文件提取出只有t1序列。提取现在文件的id序列表seqkitseqpep.fa-n-i-oft.lst将id表中的t1保

1概述首先我们需要知道一类问题，在这类问题中我们需要维护一个森林，支持加边和删边操作，然后要求维护树上的一些信息。这类问题称为动态树问题。而LCT，即Link-CutTree，就是用于解决动态树问题的一种数据结构。它可以以\(O(n\logn)\)的均摊复杂度解决这类问题。学习LCT之前

非常重要的东西我甚至模拟赛都不打了来打笔记很简单啊，朴素lca是这样，两个节点，先令深度相等，然后一个一个往上跳直到跳到相同的位置则那个点为两点的lca但是令深度相等与往上跳的过程都要一个一个慢慢跳所以时间复杂度拉满了那么我们能以什么方式优化呢我们可以发现，每个数都可以

2025省选模拟5T1、Giao徽的烤鸭又是树上问题，选择一个点的代价是$w_i$，选完所有点之后对于每个点$i$，找出最大的$d$，使得$d$满足$dis(j,i)\led$的所有点$j$全部被选，那么你就可以获得$v_d$的收益，求最大净收益。肯定是树上$DP$，我们考虑它有什么

点分治前置芝士：树的重心树的重心指对于一棵无根树上的一点，其分割开的若干子树大小的最大值最小。一般用DFS求解树的重心。初始时，\(\mathit{mxs}=\mathit{sum}=n\)，即树的节点个数。最终的\(\mathit{rt}\)即为重心。voidgetrt(intu,intfno){ ints=0; siz[u]=1; for(i

\(\text{LOJ\#6041.「雅礼集训2017Day7」事情的相似度题解}\)解法一由parent树的性质得到，前缀\(s_i,s_j\)的最长公共后缀实质上就是\(i,j\)在SAM中的\(\operatorname{LCA}\)在SAM中的\(\operatorname{len}\)。让我们考虑如何处理\((l,r)\)区间内的询问。直

\(\text{P4770[NOI2018]你的名字题解}\)注意到\(l=1,r=|S|\)有整整68分的高分，让我们先来考虑这样的特殊情况。这样的特殊情形实际上要我们求的是\(t\)有多少个本质不同的子串满足其不是\(s\)的子串。正着做看上去有些困难，于是维护\(s,t\)的本质不同公共子串个数，用

1月14日构造题训练Problem-B-CodeforcesProblem-D-Codeforces二分Problem-C-Codeforces优先队列下午小希的迷宫-HDU1272-VirtualJudge并查集判环典题，但是有细节，n=0&&m=0输出yes(唐)。#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'

给定数组a[n]，初始时a[i]=i，有q次操作：操作1、1xy，表示合并x和y操作2、2xy，表示合并区间[x,y]操作3、3xy，表示询问x和y是否在同一个集合1<=n<=2E5;1<=q<=5E5分析：可以用set+并查集来做，这里用区间并查集来做，在普通并查集的基础上增加ne变量，来维护下一个没合并的位置，用于操作2

\(\text{P3247[HNOI2016]最小公倍数题解}\)第一眼上去没什么明显的思路。图上问题一般没有什么好的多项式复杂度算法来解决。观察数据范围，注意到\(n,q\le5\times10^4\)，是一个典型的根号复杂度算法，于是考虑分块来处理。注意到所求的不一定是简单路径，也就是在不超过所需要的

线段树分治-学习笔记阅前须知：本文给出了线段树分治的一道例题以及多道习题，同时给出了部分实现的代码，帮助学习线段树分治。总述线段树分治是一种离线算法，在于把修改挂在线段树的节点上，通过遍历线段树求出每个叶子节点的答案，以减小复杂度。例题P5787二分图题目大意：\(n\)个点

[NOI2018]你的名字Solution：考虑一下\(l=1,r=\left|S\right|\)的时候怎么做，其实比较简单，我们对\(S,T\)都建立出SAM，利用这个求得\(p_i\)，表示\(T_{i-p_i+1,i}\)在\(S\)上是一个连续子串，设\(fir_i\)表示\(T\)的SAM中，节点\(i\)代表的\(endpos\)中的最小值（事实上

个人感觉各方面难度高于《在美妙的数学王国中畅游》，也不知道是不是求导的关系，这题\(luogu\)难度评级还更低。不过感觉这题作完对\(LCT\)理解更顺畅了。前四个操作简单，关键在第五人格操作。注意力惊人的注意到我们无法像普通\(Splay\)一样，直接对\(LCT\)中的\(Splay\)

思维题训练https://codeforces.com/contest/1800/problem/E1https://codeforces.com/contest/1800/problem/E2这两题很经典，两点间的交换看作两点在一个连通块，用并查集建边。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e6+10;intfa[

 由于无法提交题解所以来csdn蹭个位置  题目链接  这道题我的思路就是用并查集(推荐先学习：并查集（B站视频))将所有农场连接成n个(几个都不重要)连通块，用一个优先队列(由于作者没找视频所以不放链接了sorry)记录x农场连接y农场的最小价格。  有个值

最大值最小的路径肯定在最小生成树上，考虑用\(LCT\)维护最小生成树，只需要维护长度最长的边即可实现。由于\(LCT\)维护最小生成树不支持删边，所以采用倒序加边的方式处理。时间复杂度\(O(n\logn)\)。#include<bits/stdc++.h>#definefa(x)lct[x].fa#definefl(x)lct[x].f

上午思维题训练https://codeforces.com/contest/2026/problem/Chttps://codeforces.com/contest/2026/problem/Bhttps://codeforces.com/contest/2023/problem/Ahttps://codeforces.com/contest/2034/problem/D下午https://vjudge.net/problem/HDU-4612题意：有一个无向图，加

一眼树链剖分或\(LCT\)，由于在学后者所以就写了。取反操作相当于把\(min,max\)取反后交换，所以要维护\(min,max,val\)。时间复杂度\(O(m\logn)\)。#include<bits/stdc++.h>#definefa(x)lct[x].fa#definefl(x)lct[x].fl#definemx(x)lct[x].mx#definemn(x)lct[x]

atcoder杂题#05abc340_gLeafColorabc340_fF-S=1abc361_gGoTerritoryabc386_fOperateKabc340_g独立想出了这道题。如果我们确定了子图的叶子，那么这个子图就确定了。又由于叶子的颜色要相同，所以每种颜色的贡献是互相独立的。首先如果一种颜色有\(x\)个点，那

CF补题950-Div.3-20250102Dashboard-CodeforcesRound950(Div.3)-CodeforcesA：题目大意：给出一个字符串，要求重复的字母必须\(\gem\)，求缺失字母总个数#include<iostream>#include<map>usingnamespacestd;map<char,int>mp;intmain(){ intT; cin>&g

啊啊啊啊啊啊啊啊啊啊啊我终于改完啦啊啊啊啊啊啊啊。因为没有在最开始的时候将所有点设置为已经重构的，所以直接\(R15-R70\)间卡了两三天。似乎也是我第一次大规模使用指针了。这道题假如只有一次询问，就是一道简单淀粉质，直接在根节点建立平衡树，记录\(r_x-dis(x,rt)\)，然后找

板子合集头文件//5oiR5piv6YKj57u06I6x54m555qE54uX#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;constexprintN=-1;constexprintinf=20241218;stack<char>t;intmain(){// freopen("neuvill