祝馀宫

题面题目链接大秦 为你打开 题目传送门 题目翻译给一棵 $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$ ，就可以了 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 ...

题面大秦为你打开题目传送门 题目描述小 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]$ 即可。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293 ...

题面题目链接大秦 为你打开 题目传送门 备用题面给定一颗 $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] ...

题面题目链接大秦 为你打开 题目传送门 备用题面给定一颗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 maxim ...