祝馀宫

题面题目链接大秦 为你打开 题目传送门 题目翻译有一棵树，初始有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 ...

2024-517集训总总结还好。 关于题目的那些事算法方面十天集训，只有两道 $\tt DP$ 还压在最后一天。。。。。。真的是短板了现在。。。 其他的算法都还好，正解都能想出来，AK两次其他基本都是榜前3 码力方面代码打完还能有一至半小时空闲划水，这个问题真的不大。 难度方面个人认为偏简单，难题都压在二期了。还有就是。。。这出题人尼玛包完原神的，题题原，纯若至 关于平时的饭菜很难评。。。中午饭吃的有点山寨。。。晚饭还好。 关于我们住的宿舍还好，没想象中的那么差，没想象中的那么好。 关于一些玄学设备空调很凉快，插线板也没有以前那种不够用的情况。桌子有点小，其他还好。 关于大佬我周围的都是大佬，就我最菜，菜飞了，天天他们AK了我才AK，，，，，rzrzrzrz 周泽共

比赛总结发挥基本正常，T3 超级无敌尼玛比大失误 T1 总结赛时总结简单题，纯模拟即可 题目思路模拟 题目代码无 T2 总结赛时总结一眼题。小学生题目，模拟 题目思路模拟 题目代码无 T3 总结赛时总结赛时思路基本正确，结果为了计算正确的转弯次数多此一举，WA + TLE 0 分。 题目思路记忆化搜索 题目代码无 T4 总结赛时总结知道是前缀和，但是摆烂 题目思路从 $k = 2$ 的情况扩展出来，变成了简单的小学题 题目代码无 CSP - S 2022 题解T3 星战（Galaxy）题意给出一张有 $n$ 个点，$m$ 条边的无向图。有如下几种操作。 摧毁一条边 修复一条边 摧毁一个点以及其所有的边 修复一个点以及它所有的边 思路和哈希或异或哈希。处理每一个点的入度，与满图状态比较。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787 ...