祝馀宫

题面题目链接大秦 为你打开 题目传送门 备用题面给一棵 $n$ 个节点的树, 节点编号为 $1$ ~ $n$ ，每条边有权值。 对于一棵树，最长的路径为树的直径，可能不唯一。 求该树的直径长度是多少，以及有多少条边满足所有的直径都经过该边。 思路首先直径肯定都会算，我们记录一个答案，把直径的一个端点作为根建树，然后对于每一个点记录一下该节点的子树中到根节点最远的是多远，顺便记录一下一共有几个，如果当前点是直径上的点的话我们先判断一下是否存在两个及以上最长路径，如果是的话答案缩小到深度减一，如果存在子树中到根节点的距离的最大值等于根节点到该点的距离，我们直接将答案减去深度减一直接输出即可。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210 ...

题面题目链接大秦 为你打开 题目传送门 题目翻译给一棵 $n$ 个节点的树，节点编号为 $1$ ~ $n$ ，每条边权值都为 $1$ 。 另给定一个整数 $k$ ，求距离刚好为 $k$ 的点对有多少。 注：$(u,v)$ 和 $(v,u)$ 算同一个点对。 思路我们设 $dp[i][k]$ 表示距离 $i$ 号点距离为 $k$ 的点的数量。那么显然的可以得到转移方程： dp[root][j] = \sum dp[son][j-1]但是这时候只有我的子树方向的点，所以还要算上不是我的子树方向的点，那就是： dp[root][j]=dp[root][j]+dp[son][j - 1] - dp[root][j-2]然后这样就是统计和然后除以 $2$ ，就可以了 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 ...

题面大秦为你打开题目传送门 题目描述小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是 $E_S$，那么需要满足：($value(e)$ 表示边 $e$ 的权值) $\sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)$。 这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。 输入格式第一行包含两个整数 $N$ 和 $M$，表示无向图的点数与边数。 接下来 $M$ 行，每行 $3$ 个数 $x,y,z$ 表示，点 $x$ 和点 $y$ 之间有一条边，边的权值为 $z$。 输出格式包含一行，仅一个数，表示严格次小生成树的边权和。 样例 #1样例输入 #112345675 61 2 1 1 3 2 2 4 3 3 5 4 3 4 3 4 5 6 样例输出 #1111 提示数据中无向 ...

题面题目链接大秦 为你打开 题目传送门 题目翻译有一棵树，初始有4个结点： $1,2,3,4$ 。其中 $2,3,4$ 的父亲都是 $1$ 。 有 $q$ 个操作，每个操作给出指定的一个叶子结点 $v_i$ ，设当前操作执行前树中有 $n$ 个结点，然后添加结点 $n+1$，$n+2$ 号为 $v_i$ 儿子，添加完成之后树变成了 $n+2$ 个结点。 现在要求计算每次操作之后树的直径是多少。 思路因为每次增加两个同一个叶子节点的儿子，每次直径最多延长 $1$ ，直接对比选择那个节点后可以得到的最长直径即可（这题尼玛比卡常，得 O2 + O3 + fastIO 才可以过） 还有就是有一个细节，每次增加两个点，数组得开到操作数 $\times 2$ 。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888 ...

题面大秦为你打开题目传送门 题目描述给一棵n个节点的树, 节点编号为1~n。 给定m条路径，问最多可以选多少条路径而且他们不经过同一个点。 题解这道题目很显而易见是一道贪心题目，我们借鉴类似于在区间上选择最多线段的题目的思路，不难想到策略：选 LCA 尽可能深的路径。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152/** * @file HD ...

题面题目链接大秦 为你打开 题目传送门 题目翻译给一棵n个节点的树, 节点编号为1~n。 树上的结点要么是黑色，要么是白色，每次可以把连通的一种颜色变成另一种颜色。求至少要多少次，才能是整棵树变为一种颜色。 思路不难发现，如果我们把两个相邻的点是否相同作为边权，这道题目其实就是求出这棵树的直径上有多少种成对的不同的颜色。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113/** * @file CF734E.cpp * @author Zhoumouren * @brief * @version 0.1 * @date 2024-08-22 * * @copyright C ...

题面大秦为你打开题目传送门 题目描述给一棵 $n$ 个节点的树, 节点编号为 $1$ ~ $n$ ，每条边都有一个花费值。 有 $k$ 个机器人从 $s$ 点出发, 问让机器人遍历所有边，最少花费值多少？ 题解这道题目一眼树形 DP ，那么问题就是，怎么设置状态。我们设 $dp[i][j]$ 表示 $i$ 号点上面有 $j$ 个机器人的最小花费。那么就有转移方程： dp[root][j] = min(dp[root][j-k] + dp[son][k]+k\times edge\_weight)这个的意思就是，我这里当前有 $j$ 个机器人，分出来 $k$ 个给儿子走下去。初始化定义一下 $dp[i][0]$ 即可。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 ...

题面题目链接大秦 为你打开 题目传送门 备用题面给定一颗 $N$ 个节点的树，结点从 $1$ 到 $N$ 编号。 现在要计算对于每个结点 $i$ ，到它最远的结点是多少距离。 思路显而易见的，树上最远的点对是树的直径的两个端点。而学过小学数学的人都知道，从 $i$ 点出发，经过最远的一条链的一部分，最后到达这条最远链的两个端点之一一定是最长的。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122/** * @file P2386C.cpp * @author Zhoumouren * @brief * @version 0 ...

题面大秦 为你打开 题目传送门 题目翻译：给定一颗 $N$ 个节点的树，结点从 $1$ 到 $N$ 编号，每个结点上有一些苹果。 现在从结点 $1$ 开始，每一步可以走向相邻结点，到达某一结点后，可以收集该结点的苹果（第二次到达某结点则没有苹果可收集）。 现在最多可以走 $K$ 步，问最多可以收集到多少苹果。 思路这是一道很典型的树形 DP ，它要求我们从 1 号点开始最多走 K 步的经过的点的权值之和最大值，重复经过的节点只算做一次。不难设计出状态：$dp[i][j][0/1]$ 表示从 $i$ 号点出发，走了 $j$ 步，最后返回 (1) 或不返回 (0) 的最大价值。 那么接下来就是画图环节，自行绘画理解。 $dp[root][j][0]=max(dp[root][j-k][1]+dp[son][k-1][0])$ 该方程表示在root出发走root的除son之外的子树走了j-k步并且回到root，然后从root出发到son要一步(所以k-1)，再从son出发走k-1步不返回son。 $dp[root][j][0]=max(dp[root][j-k][0]+dp[son][k-2 ...

题面题目链接大秦 为你打开 题目传送门 备用题面给定一颗n个节点的树，每个顶点有权值。 现在要求选出若干点，这些点不能有边直接相连，使得权值之和最大。 思路这道题显而易见的是一道经典的树形DP题目。直接设 $dp[i][0/1]$ 表示 $i$ 号点选 ( 1 ) 或不选 ( 0 ) 的最大值，DFS深搜做DP即可。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071/** * @file 517P2386A.cpp * @author Zhoumouren * @brief * @version 0.1 * @date 2024-08-21 * * @copyright Copyright (c) 2024 * Set the dp[i][0/1] to calc node i choose (1) or not choose (0) the maximum we ...