CF917D Stranger Trees
Codeforces Luogu 算法一 分析 设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。 然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Codeforces Luogu 算法一 分析 设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。 然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可...
Codeforces Luogu 分析 我们把每个连通块看成一个点，然后用 Prufer 序列计数。那么方案数为 用并查集求出连通块个数及每个连通块的大小即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ============...
Luogu LOJ 分析 考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。 于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。 又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。 这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所...
Luogu LOJ 分析 可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量（这里一条边也算点双）的并。 那么对于一对 $(s,t)$，满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。 考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树，可以想到将方点的权值设成点双大小，圆点的权值设成 $-1$...
Luogu LOJ 分析 Subtask1 在某个物品旁边放上一个蓝色石子，这样子 Koala 就只能得到至多 $99$ 个物品，而没选的那个物品一定是权值最小的。 这样子只需要调用一次 playRound，可以得到 $4$ 分。 Subtask2 先在每个物品旁边放 $1$ 个蓝色石子，这样子 Koala 会选出至多 $50$ 个物品，所以我们可以确定权值前 $50$ 大的物品。 那么可以...
Luogu LOJ 分析 因为期望具有线性性，所以可以对每个节点计算它在 $k$ 次操作后有标记的概率，全部加起来即为答案。 考虑 DP。设 $f_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后有标记的概率，$g_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后某个祖先有标记的概率，$h_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后自己和祖先都没有标记的概率。 转移需要再求...
Codeforces Luogu 分析 显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内，所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。 显然每个强连通分量内成环最优，那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数，则应最小化后面那个东西，即把一些强连通分量在满足条件的情况下合并成一个大环。 因为点数 $...
AtCoder Luogu 分析 设 $c_i=\max\left\{0,a_i-b_i\right\}$，则相当于要求任意在 $u$ 点的时刻手中都有至少 $c_u$ 円。 然后可以发现两个结论： 每个点只会在最后一次访问时被捐赠。 $c_i$ 大的会优先捐赠。 那么我们大概是这样捐赠的：首先选一个点 $u$，假设删掉 $u$ 后形成了 $tot$ 个连通块，则先捐赠掉 $tot-1$...
Codeforces Luogu 分析 显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。 考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移 于是只要快速找到决策点改变的位置即可...
Codeforces Luogu 分析 直接算即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h>...