视频链接：   P3574[POI2014]FAR-FarmCraft-洛谷|计算机科学教育新生态(luogu.com.cn)//树形DP+贪心O(nlogn)#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=500005;inthead[N],to[N<<1],ne[N<

[POI2014]TUR-Tourism题意给出一张图，在这张图中，任意两点间不存在节点数超过\(10\)的简单路径。第\(i\)个点被选的代价为\(C_i\)，每个节点要么选，要么与它直接相连的点中至少有一个被选。求最小代价。思路图的生成树上状压动态规划。由于给出的是一张图，无法直接dp，我们可

题意给定一个DAG，你需要删掉一个点使得原图的最长路径的长度最短，求出答案和方案。\(n\le5\times10^5,m\le10^6\)分析DAG的一条路径有一个优美的性质：一定是从拓扑序小的点指向拓扑序大的点。考虑按照拓扑序从小到大处理每一个点。假设我们处理到了点\(x\)，它的拓扑序是\(i

原题链接题解首先，考虑接下来往哪颗树飞是很困难的，因为当前的决策会影响之后的决策但是如果考虑到达当前树从哪里飞过来就比较好了，因为无后效性接着我们可以暴力做法，遍历每棵树从前\(k\)个树飞过来的值，然后取最小的那个，但是这样显然会超时，所以我们优化一下有哪些值得被优化

P3569KAR如何判断某个卡牌顺序能否通过反转形成一个单调不降的序列？使用贪心。我们将第一张卡牌翻到更小的一面。对于后面的卡牌，若小的一面大于等于前一张卡的当前面值，则翻到小的一面。否则若大的一面大于等于前一张卡的当前面值，则翻到大的一面。仍不满足则无解。为了对付单点

可持久化线段树维护由任意一段区间得到的权值线段树线段树的深度：\(ceil(log_{2}(n))+1\)由于询问的特殊性，我们可以直接在线段树上二分，而不需要另写查询函数，从而节省掉1个log的复杂度点击查看代码#include<bits/stdc++.h>usingnamespacestd;inttot,root[500005];int

题目描述：给定一棵树，在树上选\(3\)个点，要求两两距离相等，求方案数。数据范围：\(1\len\le5000\)\(1\lea,b\len\)思路：一开始我想的就是枚举两个点，然后处理第三个点。但是发现这样做非常的不正确，并且非常容易算重，所以我舍去了这种方式。但是在想这种做法的时候，我们会发现，

三倍经验：bzoj#3522P3565loj#2431加强版：bzoj#4543先看bzoj#3522这题。容易想到时间\(O(n^2)\)，空间\(O(n^2)\)的树形dp。设\(dp_{1/2/3,u,i}\)表示以\(u\)为根的子树中所有以\(u\)为一端点，长度为\(i\)的路径中选\(1/2/3\)条路径的方案数（

P3573[POI2014]RAJ-Rally题意给一张\(DAG\)，问删去一个点的最长路是多少。题解好妙的题。考虑对于每个点求出删除此点之后的最长路。考虑到一个\(DAG\)只会由拓扑序低的点走向高的点。所以我们按照拓扑序枚举点删除之后的最短路。考虑根据当前点的拓扑序将点集划分为

[POI2014]HOT-Hotels题面翻译给定一棵树，在树上选\(3\)个点，要求两两距离相等，求方案数。题目描述Thereare\(n\)townsinByteotia,connectedwithonly\(n-1\)roads.Eachroaddirectlylinkstwotowns.Alltheroadshavethesamelengthandaretwoway.Itis

区间\(\left(l,r\right]\)中存在\(n\)的倍数的充要条件是\(\left\lfloor\frac{r}{n}\right\rfloor>\left\lfloor\frac{l}{n}\right\rfloor\)。证明：记有整数\(k\)满足\(k\timesn\in\left(l,r\right]\)。那么有\[\displaystylel<k\timesn

网瘾犯了。https://www.luogu.com.cn/problem/P3573题意：在DAG上删除一点，使得剩下点的最长路最短。解答：用\(f_v\)和\(h_v\)表示终点为\(v\)、起点为\(v\)的单源最长路。按照拓扑序（这样才是DAG，有dp性质）枚举\(u\)，每次先删除所有以\(u\)为起点的最长路，再更新答案，

洛谷上面的题解写的真的不太好，有很多错误，我来谈谈自己的理解。设\(f[i]\)表示以\(i\)为根节点的子树中（包括节点\(i\)）的所有人安装好游戏所需要的时间（与下面的\(g[i]

Tourism容易想到跑出dfs树，这样只有返祖边，且每个点的深度不超过\(10\)。考虑状压祖先的状态，设\(f_{i,S}\)表示dfs到了\(i\)点，祖先的状态为\(S\)的最小值。\(S\)的每一位

P3565[POI2014]HOT-Hotels给定一棵树，在树上选\(3\)个点，要求两两距离相等，求方案数。原题数据范围\(n\leq5000\)，可做到线性，空间\(62.5\text{MB}\)。sub1\(n\leq