ShichikujiandPowerGrid题意还是很简单，每个点有点权，每个点之间也有边权求最小生成森林，每个一颗最小生成树的权值等于边权+最小点权思路边权我们很好处理，有模板，但如何处理这个点权，便成了主要的问题如果我们以边权的思路思考点权，那么点权就是某个点从到该点的边权而我们可

题目描述给定一棵有\(n\)个节点的树，根节点为\(1\)，节点\(i\)有权值\(w[i]\)。这棵树非常奇怪，它的每个叶子结点都有一条连向根节点的权值为\(0\)的边。给定\(q\)次询问，每次给定\(u,v\)，请计算出一条\(u\)到\(v\)的路径（每条边最多经过\(1\)次），最小化该路径上的点权之和，并在其基础上最

SS241009B.贪吃蛇（snake）题意给你一个\(n\timesm\)的矩阵，满足\(n\timesm\le10^6\)。每个点有一个权值\(a_{i,j}\)。从一个点出发，能量值是这个点的点权，然后可以走到四周比它能量小的结点，吃掉它并合并能量。问从每个位置出发，能不能吃完整个地图。思路首先显然的贪心是

\(Kruskal\)重构树解决的基本问题：一张图中\(u\)到\(v\)路径上最大边的最小值。构建：在从小到大加边的过程中，如果\(u\),\(v\)不在一个并查集中，就建立一个新的节点\(X\)，并将\(fu\)和\(fv\)分别作为\(X\)的左右儿子，\(X\)的点权就是这条边的边权。这样树，我们称为\(

点权多叉重构树Kruskal重构树不仅适用于限制边权的题目，也可以处理限制点权的情况。在某多校冲刺NOIP联训测试2021和CF1797F出现了这种方法。Alex_wei的博客进行了详细讲解。\(Problem1.\)「NOIP多校联训2021」超级加倍参考资料Alex_wei

前言今天题单里面有这个题（AGC002D）需要用到相关知识就学习了一下。以该题为例讲解一下kruskal重构树的构成与性质。构造用图片来展示构造的过程，简单来说就是将边权从小到大排序，然后给每条边的两点建出一个父亲来，父亲的点权就是原先这条边的边权，如果其中一方或双方都在某个新建

没有点权和边权的时候，不讨论最大权闭合子图，最大匹配=最小点覆盖=点数-最大独立集最小点覆盖=点数-最大独立集：这个很好理解，考虑只有一条边的二分图的情况，点覆盖要求两个端点至少选一个，独立集要求两个端点最多选一个，是互补的关系，这意味着一个合法点覆盖的点集与一个合法独立集的

令\(w_{(u,v)}\)为边\((u,v)\)的边权。考虑到对于一条边进行操作影响的是有公共点的边，于是一个想法是把边权转到点权，用点权来表示边权。于是考虑对于每个点构造\(w_u\)使得\(w_{(u,v)}=w_u\oplusw_v\)。因为这是一颗树，所以一定存在合法的构造。其实到了这里，这种

$\quad$圆方树练手好题。$\quad$大概意思就是给你一个仙人掌，其中每个点都有点权。有\(m\)次询问，其中有两种操作：回答两点间所有可能路径（不重复经过一个点）上的点权最小值、将某个点的点权改为某值。$\quad$对于路径上点权最小值，可以先转化为圆方树，然后树链剖分解决，用方点

已经不止一次了解到建图的技巧了，例如：最大流建立超级源点，超级汇点建反图，但已经忘了这个题是什么时候的题了点权转成边权2024/7/15介绍点权转边权如下所示，建立一个有\(2N\)个顶点和\(N+M\)条边（成本只分配给边）的有向图，答案就是从顶点\(1_\text{in}\)到顶点\(i_\te

7/14:昨晚打的abc，外面下着大雨；1650ptsrank975T1:简单签到题，愣是被我拖了7min死因：开赛时老师开始收手机，一直叫我名，我一着急装了两个翻译插件，导致页面错版。时间宝贵，于是我艰难的对照样例勉强读懂题（T2:计算几何？给平面直角坐标系3点，判rt三角形。直接double勾股定理算边

一句话题意：给定一个带点权的有权无向连通图，求点1到所有其它点的最短路径。首先，只有1一个起点，所以是单源最短路，又因为最大是\(2\times10^5\)，所以是优先队列（堆）优化过后的Dijkstra。所以，我们只需要解决点权的问题就好了。一种显而易见的想法是把与这条边的边权加上起终点

最多限制相交路径问题已知一些路径，每一个节点可以属于多个路径，但是属于路径的数量不得超过一个给定的上限。解决方法将\(1\)个节点拆为\(2\)个，接着进行连边，其中容量代表可以经过的路径。最大权闭合图定义如果一个点集满足其中任意元素可以到达的所有元素都在集合中，那么

CF1987E题解题意给定一棵大小为\(n\)的有根树，各点各有一点权\(a_i\)。每次操作可以选定一节点使其点权加一，求最小的操作数，使得任一节点满足其点权不大于其所有儿子的点权之和。\(n\le5000,0\lea_i\le10^9\)题解麻了，赛后十五分钟调出来，可惜为时已晚。读懂题之后

引入——最大权独立集问题：最大权独立集：对于一棵树，求出一个点集，这个点集里面的任意两个点都不相连。那么在所有这样的点集中，点权和最大的那个点集，就被成为最大权独立集。想要求出最大权独立集的点权和，我们只需要使用树上dp的方法即可实现设数组f[N][2]其中f[x][0]表示不选择

有操作的操作场，考场过了ABC（3/4）A.SugarWater题意：一个杯子，可以容纳\(F\)克糖水，一开始是空的。每次操作：加入\(100A\)克水加入\(100B\)克水加入\(C\)克糖加入\(D\)克糖每\(100\)克水最多溶解\(E\)克糖，求任意次操作后完全溶解的糖水中的最大含糖量，以

这道题目作为枚举子集的题目见识一下首先对于一个连通块，如果点权之和为\(0\)，那么我们算出MST显然就是最优解我们看一下数据范围，可能是考状态压缩我们把状态\(i\)设出来后，可以先尝试考虑某一个点，但是你发现这样不太好考虑，而且只考虑这一个点的话，那么这个点所加入的连通块的点权

分析首先发现此题的式子一看就不是很友好。所以尝试化简。原式：\(max(|a_u+a_v|,|a_u-a_v|)\)。分类讨论：当\(a_u>0,a_v>0\)时，显然有原式\(=a_u+a_v\)；当\(a_u>0,a_v<0\)时，\(|a_u-a_v|=|a_u+|a_v||\)，\(|a_u+a_v|=|a_u-|a_v||\)。肉

因为我记忆力不好，经常遇到之前做过的题一下子想不起来，所以打算基本上给每个比较有意思的题写题解，同时造福后代。这是werewolf，它是furry，很可爱题意：一张无向图，点有点权，每次询问从\(u\)到\(v\)的路径中，是否存在一条先走点权大于等于\(L\)，再走点权小于等于\(R\)的路径。思路

关于我在赛场上一题都没有切，后面自己推出来正解这件事~题面翻译给定一个长度为\(N\)的整数序列\(A=(A_1,A_2,\cdots,A_N)\)和另一个长度为\(N-1\)的整数序列\(P=(P_2,\cdots,P_N)\)。注意\(P\)的索引从\(2\)开始。对于每个\(i\)，保证\(1\leqP_i<i\)。现在您

915-F题目大意给定一棵\(n\)个节点的树，节点带权，设函数\(I(x,y)\)等于点\(x\)到点\(y\)的路径上最大的点权与最小的点权之差。求：\[\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)\]Solution令函数\(F(i,j)\)等于点\(x\)到点\(y\)的路径上最大的点权，函数\(G(i,j)\)等于点\(x\)到点\(y\)

诸位大佬把思路讲的很清晰了，我主要补充一下实现。思路考虑：如果一个询问的答案是肯定的，它对路径上所有点的要求。询问为abe。因为只有\(e\)点能量，所以能走到的最大高度只有\(h_a+e\)，没有最小高度。若路径上所有点的点权都在这个范围内，这个询问成立。问题转化成：\(a\)

洛谷题面感觉有点毒瘤，不过还是有些trick在的。题意翻译（复制于洛谷题面）：给定一个\(N\)个点\(M\)条无向边的图，图上每个点都有其颜色。求所有经过点权单调不降的路径中，出现的不同颜色的个数最多是多少。由于是单调不降的路径，所以可以点权大的点到点权小的点的路径对结果没

挺简单的知识点（？）概念首先Kruskal算法是用来求最小生成树的算法之一，其思想是贪心。而Kruskal重构树就是将整张图重建为二叉树。在跑Kruskal的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。首先新建\(n\)个集合，每个集合恰有一个节点，点权为\(0\)。每

Kruskal重构树一般用于求图上任意两点间距离的最值，距离为路径上边权最值。建树：将边权升序排序后，依次把点对加入树中，每次把两点当前所在的树根与一个新点连边，点权为原边权，然后新加的点成为树根。例如，对于以下最小生成树：它的Kruskal重构树为：性质：对于原图上的两点，它们的距离