题目顺序不是做题顺序也不是考试顺序更不是难度顺序，是随机顺序。
为了不影响观看体验决定把代码删去，需要请私信我，QQ或博客园皆可。
题目里的难度评分是个人评分，仅供参考开心就好。
林克卡特树(LCT)
难度评分：(NOI-)
题意是有一棵树上有边权，边权可正可负，要求删去(k)条边同时加上(k)条边权为(0)的边，然后选出树上一条路径((p,q))，获得(sum_{i∈path(p,q)} v_i)的价值，最大化这个价值。
先考虑一下部分分，发现(k=0)就是树的直径。那么删去(k)条边实际上就相当于构成了(k+1)个连通块，在每个连通块里面求直径累加起来即可。于是考虑(60pts)的部分分，发现可以打一个(O(nk))的暴力。这种暴力一般是树形(dp)。
考虑怎么设树形(dp)的状态：设(f[i][j])表示以(i)为根的子树里选出了(j)条链。这个链有两种：经过根和不经过根。问题是不同子树里面的链怎么拼在一起？记录首尾肯定不行。所以问题就出在了状态无法转移，但是部分分放在那里肯定是让你写的。于是思考一下链的特殊性质，链上所有点的度数( leq 2)。于是考虑加入度数限制，只要有点被选择的时候度数已经为(2)就肯定不合法。
再考虑转移：
① ((u,v))不选择：(u,v)两点度数不变，路径条数累加，(dp)值累加。
② ((u,v))选择：（(path)表示路径条数）
·如果(deg_u geq 2)或(deg_v geq 2)就不能选择。
·如果(deg_u=deg_v=0)，那么(path++)
·如果(deg_u=deg_v=1)，那么拼成了一条新路径，(path--)
·如果(deg_u=1,deg_v=0)或(deg_u=0,deg_v=1)，相当于延伸一条路径，(path)不变
然后(dp)值累加即可。
但是我们还是漏掉了一种情况，因为一个点就是一条退化的链，而这样(dp)我们是不考虑单点只考虑边的。翻看题解我们想到把一个单点进行度数限制，于是我们假设选单点(=)选自环，其度数为(2)，那么这个点成为单独的一条路径之后就不能和其它点进行拼接了。
考虑(dp)状态的边界：(f_{i,0,0}=0,f_{i,1,2}=0)。就表示根选了(0)条链度数为(0)价值为(0)，根被选成(1)条单链度数为(2)价值为(0)。其它的设置成(-inf)。答案为(Max(f_{i,k,0},f_{i,k,1},f_{i,k,2}))。
还有一些细节需要慢慢调，做完这些大概可以拿到(60pts)。
然后考虑满分做法（参考了(Troywar)的博客）：
我们将连通块数作为(x)轴，最优解作为(y)轴，则图像是一个单峰上凸函数，同时相邻两点间斜率递减。证明：假设当前连通块数为(x)，当它变为(x+1)时，必然是在(x)时的最优解上再连接一段新的可空路径并切掉一部分可空路径，当补上一条新路径时，由最优性可知，这次加上的路径(-)切掉的路径所获得的价值一定比原来小。于是相邻点之间的斜率肯定是单调递减的。
考虑二分这个斜率并将图像减去斜率对应的正比例函数，那么新图像的最高点将会在这个斜率对应点的位置，同时也是一个斜率递减函数，这时候答案为：（新图像上最高点的）权值(+)连通块数( imes)斜率。如何计算？回想(dp)过程，我们把第二维的(k)去掉，设为(f[i][0/1/2])，含义即(60pts)中提到的表示(i)的度数为(0/1/2)时的最优解和连通块个数。当(i)自己为一个连通块的时候，(2)就表示这三个状态的最优解。
考虑新的转移：（写累加的就是(+=)，不写累加的就是取(Max)）
①(f[u][0])：
·累加(f[v][2])
②(f[u][1])：
·累加(f[v][2])
·(f[u][0])和(f[v][1])的合并
·(f[u][0])和(f[v][0])的合并
③(f[u][2])：
·累加(f[v][2])
·(f[u][1])和(f[v][0])的合并
·(f[u][1])和(f[v][0])的合并
然后这是带权二分，用(wqs)二分即可。得到结果后与(k+1)个连通块时的最优解比较大小，如果大于说明斜率过小还可以调大，否则调小。
(IIIDX)
难度评分：提高(+)
题意是给定(n,k)以及(n)个数(d_1,d_2,cdots ,d_n)，其中(k)是小数其余是整数，要求求出一种排序方式满足(forall d_i geq d_{lfloor frac{i}{n} floor})，而且在合法情况下越靠前值越大越好，要求输出方案。
(55pts)肯定是把(lfloor frac{i}{n} floor)和(i)之间连边，然后贪心一下：(dfs)回溯的时候赋予栈顶目前可用最大值就行。
满分做法的关键在于遇到相同的怎么处理。我们假设我们得到了子树的(dfs)序，然后我们把所有权值从大到小排序。考虑对于一个(x)，我们在什么情况下把(x)赋给(i)：当且仅当(geq x)的且还没被拿来使用的数(geq size_i)，其中(size_i)表示以(i)为根的子树大小。为什么呢？因为至少(i)的子树里面的数都(geq i)所拥有的值，也就是至少(size_i-1)个数比(i)要大。然后我们假设我们为(i)的子树预留了一些值，虽然不知道预留了哪些值，但是一定预留了(size_i)个值，所以提前透支掉后面的，把后面可用的减去(size_i)个。于是我们用线段树维护对于(i)，当前可用的放在(i)子树里面的值，然后在线段树上二分即可。
秘密袭击(CoaT)
难度评分：提高(+)
题意是给定一棵有点权的树，在树上选出一些点可形成连通块，求所有连通块的第(k)大权值和(mod 64123)。
这个题的官方正解非常复杂，是线段树+(FFT)，实际上完全可以按照优化暴力的思路去解决问题。
首先考虑暴力，枚举一个第(k)大权值(val)，然后树形(dp)算出来多少个连通块有(geq k)个(geq val)的值。这样做复杂度难以承受。
考虑优化这个暴力，二分不太行，但是可以缩小枚举范围，就是枚举到最多(k)个值(geq val)的那个(val)就行。然后(dp)的时候不考虑(< k)的，直接考虑(geq k)的方案数。这样优化基本就能过了。
劈配(mentor)
难度评分：提高
题意是给定(A,B)两个集合，给出(A)想要的(B)中的元素并且按照喜爱度排序，优先要喜爱度高的(B)，以及(B)最多同时被多少个(A)中的元素拥有并且(B)优先要排名高的(A)，请求出最优方案，以及每个(A)的排名要往前多少才能满足他的理想(B)。
首先看数据范围(n,m leq 200)，就知道这是送分题。由“两个集合”的提示想到二分图匹配，但这个题有很多备选匹配，怎么办呢？利用匈牙利算法的思想，我们匹配一个人和他现在的理想导师，如果导师的弟子没满就直接配给他，如果满了就试试看能不能挤掉导师的一个弟子让这个弟子去匹配。在求的过程中顺便记录答案就行了。
一双木棋(chess)
难度评分：普及(+)
一看(n,m leq 10)，直接(Min-Max)搜索(+ alpha - eta )剪枝即可。
制胡窜(cutting)
难度评分：(NOI-)
题意是给定一个字符串，(m)次询问每次一个区间([l,r])，让你求出有多少合法的(i,j)，满足把整个字符串分成([1,i],[i+1,j-1],[j,n])三个部分，使得每个部分都含有([l,r])。
做法(1)是考虑容斥，(+)至少左边/中间/右边有的，(-)左中/左右/中右有的，(+)左中右都有的。
做法(2)是正难则反，也就是用总的(-)不合法的。
我用的是做法(2)。还是考虑不同段的贡献。可以先找到出现串([l,r])的最早结束位置和最晚结束位置（后缀树上倍增对应到相应位置的线段树上再在线段树上二分即可）记为(lpos,rpos)，于是(ans=sum_{i=lpos}^{rpos} )第一次出现与第(i)次出现的交( imes)最后一次出现与第(i+1)次出现的交。
但还要考虑两种特殊情况：
1、较靠前的断点不切断任意的字符串，那么它一定在询问串第一次出现之前，并且第二个断点要恰好切断所有字符串，第二个断点的取值范围是询问串所有出现位置的并。
2、较靠前的断点切断了所有的字符串，那么较靠后的端点只需要满足在较靠前的断点之后即可，那么可能的方案数是一个等差数列的各项之和。
所以我们对(i=lpos,i=rpos)特殊处理，其他的(i)就计算(sum_{i=lpos+1}^{rpos-1} (R_{i+1}-R_i) imes (R_{i+1}-L_{last}+1) )，其中(L_i,R_i)表示第(i)次出现这个串的位置的左右端点。然后相邻位置的信息可以在线段树上就顺便维护出来。
注意是数字串(QwQ)。虽然说起来不难但是细节特别多。