查询第kkk大/小，首先想到主席树，每棵主席树记录当前节点到根节点的路径上面的所有值，每次查询u,vu,vu,v，我们使用第u,v,LCA(u,v),fa[LCA(u,v)]u,v,LCA(u,v),fa[LCA(u,v)]u,v,LCA(u,v),fa[LCA(u,v)]棵主席树，做一次差分即可。 主要是如何实现连边，最暴力的方式是把yyy所在的联通块的节点全部一个一个连到xxx上面，同时...

传送门 本质一样的一道YNOI 首先明确一件事情，这个换根其实是吓你的， 1.1.1.只有最近的一次换根才会对答案有影响（显然） 2.2.2.分情况讨论，我们始终以111节点为根，设现在查询的节点为uuu，上一次换根的根为rtrtrt（rtrtrt是一个假的根） ，我们画出333个图： 若u==rtu==rtu==rt，显然现在查询的是整棵树，对应到区间[1,n][1,n][1,n]： 若...

洛谷 LOJ BZOJ 首先，考虑这样一个问题：给你一个序列{ai}\{a_i\}{ai​}，和四个数l1,r1,l2,r2l1,r1,l2,r2l1,r1,l2,r2，求区间[l1,r1]，[l2,r2][l1,r1]，[l2,r2][l1,r1]，[l2,r2]中相同的数有多少对。 这个可以参见我出的一道题：相同颜色对 当然你不能维护四个指针，考虑容斥原理，我们不妨设f(x,y)f(x,...

传送门 考虑先把这张图的最小生成树GGG建出来，假设查询的边为EEE， 发现： 1.1.1.如果EEE本来就在GGG里面，那么直接输出GGG的边权和，因为没有比这个更优的解。 2.2.2.如果EEE不在GGG里面，那么EEE一定和GGG 形成一个环，根据贪心的原则，我们把这条环上面最大边权的边删去，这样新的图仍然是一棵树，而且边权和最小。 在实际操作过程中，我们并不用找到那个环，可以这么想，...

传送门 扫了一眼题解，发现没有一个严谨证明的，那么我就来证明一波吧。 首先，我们看一看如何求树的直径： 1.1.1.随便定一个根节点，第一遍bfsbfsbfs求出树中深度最深的节点，记为uuu。 2.2 .2.以uuu为根节点，第二遍bfsbfsbfs求出树中深度最深的点vvv 3.3.3.树的直径的端点即为u,vu,vu,v 类比到此题： 我们把政党ppp中的牛最深的记为max⁡p\ma...

传送门 这道题我们使用权值线段树合并，节点[l,r]​[l,r]​[l,r]​存的是第l...r​l...r​l...r​种救济粮的最大值val​val​val​，还要记录最多的救济粮的种类pos​pos​pos​，这个维护起来很简单，不再赘述。 考虑树上差分，每个节点开一个权值线段树，我们把节点xxx，yyy的救济粮数目+1+1+1，把节点lca(x,y)lca(x,y)lca(x,y)，...