联考 Round 1
A
场切题，把部分分全打完，发现是脑残题，消愁了。
算法 1
期望得分：\(30pts\)。
把每个点分别删去，看剩下的图是不是棵树。
算法 2
期望得分：\(20pts\)，结合算法 1 可以得到 \(50pts\)。
输出所有度数为 \(1\) 的点。
算法 3
期望得分：\(20pts\)，结合算法 1,2 可以得到 \(70pts\)。
显然原图是一个基环树，画一棵线段树，显然你选的这条边删去后必然达成了“破环”的效果。
所以，你必然要选择环上的一个点。然后因为最后是棵树，所以你要选度数为 \(2\) 的点。
瓶颈在 dfs 找环，时间复杂度 \(\mathcal O(n)\)。
算法 4
期望得分：\(100pts\)。
最后删完的图必然有 \(n-2\) 条边，所以必然要删去 \(m-(n-2)\) 条边。也就是这个点的度数是 \(m-n+2\)。
然后因为是棵树，所以必然联通，这个点还必须不是割点。
因而，只需求出度数是 \(m-n+2\) 且不是割点的点即可。用 Tarjan 实现，时间复杂度 \(\mathcal O(n+m)\)。
B
算法 1
期望得分：\(35pts\)。
显然你发现，对于每头牛，你希望他的深度越小越好。所以我们希望在有牛的情况下，每条边都被占满。然后时间轴具有交换律，也就是说，你可以假设 \(t\) 的时间同时进行，或者说把每条边的容量都 \(\times t\)。
所以考虑一种给定了 \(t\) 以后的树形 dp。
对于 \(dp_u=c_u+\sum_{v\in son_u} \min(dp_v,m_v\times t)\)
时间复杂度 \(O(qn)\)。
算法 2
期望得分：\(100pts\)。
考虑 \(g_u=m_u-\sum_{v\in son_u} m_v\)。
发现，在所有 \(g_i>0\) 的点中，\(\lfloor \frac {c_i} {g_i} \rfloor\) 最小的点 \(i\) 一定先把牛送完。牛送完之后把点 \(i\) 用并查集合并到点 \(f_u\) 上，用并查集维护合并的过程即可。
用堆维护所有 \(g_i>0\) 的点的 \(\lfloor \frac{c_i}{g_i} \rfloor\) ，把询问排序，处理 \(<t\) 的时刻的合并，合并后的 \(c_1-g_1\times t\) 就是答案。
C
算法 1
期望得分：\(36pts\)。
设 \(dp_{i}\) 表示前 \(i\) 个数的分组方案树。
转移方程为：
算法 2
期望得分：\(16pts\)，结合算法 1 可以得到 \(52pts\)。
设两种不同的 \(a_i\) 分别记为 \(p,q(p<q)\)。
预处理距离 \(i\) 最近的 \(j\) 满足 \(a_j \neq a_{j+1}\)。
也就是对于 \([a_{j},i]\) 包含了所有的两种 \(p,q\)，然后同时还要满足 \(p\le i-j+1\leq q\)
所以对于 \(a_i\)，会对他产生贡献的 \(j\) 一定在 \([1,j] \cap [i-q+1,i-p+1]\)，这显然是一个连续段，可以通过树状数组维护。
注意一个特例：在 \([j+1,i]\) 这一段，全部都是 \(p'\) 且 \(j+1\le i-p'+1\le i\)，则 \(dp_i\) 还要额外加上 \(dp_{i-p'+1}\)。
算法 3
期望得分：\(16pts\)，结合算法 1,2 可以得到 \(68pts\)。
因为没有上限，\(len\) 在增长的同时，\(\min{a_i}\) 只会越来越小，满足条件的 \(j\) 必然构成一个 \([1,r]\) 的区间。
所以，二分出这个 \(r\)，然后用树状数组维护即可。时间复杂度 \(O(n\log n)\)。
算法 4
别急让我找 jzy 学学。
D
算法 1
期望得分 \(65\) 分。
显然当前的坐标和学会的方言一定都是连续的区间，因为想要走到区间外的某个村庄时，走回去找那位老者学习就行了。
记一下当前的坐标和方言区间，随便 DP 一下就是 \(O(n^4)\) 或者 \(O(n^3)\) 的了。
标签：得分,期望,复杂度,Round,算法,条边,联考,dp From： https://www.cnblogs.com/wtc-qwq/p/18076775