$n$ 个点 $n$ 条边的联通图是一棵基环树，边由 $n-1$ 条树边加上一条环边组成。

Trick

• 拆出一条环边，剩余当成树做。

• 抠出整个环，环上每个点挂了一棵子树，先做 Tree dp，在环上做序列 dp。

妙啊！

题意

给了一个 $n \times n$ 的网格，第一行排着 $n$ 个青蛙，青蛙同时往上跳。

每行有一个线段，一个线段当且仅当完全覆盖一行时是好的，一个青蛙上跳的过程不能经过超过 $10$ 个坏的线段。

每个线段的每个位置等概率出现一个糖果，求每个青蛙恰好拿到一个糖并且能够走完全程的概率。

其中 $1 \le n \le 1000$。

分析

如果一个青蛙上面有超过 $10$ 个坏线段，显然概率为 $0$。

显然，每一行和每一列恰好有一个糖。

我们从左往右按列 dp，记 $dp[i][s]$ 表示当前到达第 $i$ 列，状态为 $s$ 的概率。

状态代表这列的坏线段依次选与不选，转移时需要将当前列的状态改变成下一列状态，并且需要判断掉一行终止且未选的无效情况。

转移时，将当前状态加到改变后的状态，并枚举下一列的一个位置进行选择，条件是不在当前列上或者当前列未选。

最后，计算出了所有坏线段的情况，乘上好线段的阶乘，即坏线段确定后，好线段可以任意取。

题意

给定 $n$ 条线段和 $m$ 个询问点，任意取出一些线段，使得所有询问点可以被不同的线段覆盖，即不能有两个点只被一条线段覆盖，求最少要取出多少线段满足这个条件。

其中 $2\le n,m \le 10^5$。

题解

赛中冲的算法是线段覆盖，对目标点询问未被覆盖次数，取 $\min$ 后加一。

显然非常的假，你不能保证剩余的线段一定能覆盖所有其他的点。

将线段端点和询问点，拆成事件做扫描线，对于相同端点的事件，先加入，再询问，最后删除。

对于询问，看能不能覆盖这个点，即有当前存在事件集合非空，答案是线段数减去集合大小，并要拿去一个线段，因为这个线段不能对其他询问产生贡献。这里需要贪心的想，右端点应该尽量靠前，这样才会减少对后面询问的影响。