标签 缩点 下的文章

「Codeforces 1138E」Museums Tour

题目链接：Codeforces 1138E

在国家 $N$ 中，有 $n$ 个城市通过 $m$ 条单向道路连接。尽管这个国家看起来并不是那么引人注目，但是这里有两件很有意思的事情。首先，这里的一周有 $d$ 天；另外，每个城市恰好有一个博物馆。

旅行社的员工知道每个博物馆的开放日期，他们正在为游客们制定一项新的旅游计划。旅游从标号为 $1$ 的首都城市出发，并且旅游的第一天必须在某一周的第一天。每天白天，如果当前城市的博物馆开放，那么游客可以进入博物馆参观；否则什么都做不了。晚上，游客要么结束旅游，要么通过道路前往下一个城市。注意，旅游过程中允许重复经过同一个城市。

你需要为旅游制定一条路线，使得在旅游期间参观的不同博物馆数量最多。

数据范围：$1 \le n \le 10 ^ 5$，$0 \le m \le 10 ^ 5$，$1 \le d \le 50$。

「Codeforces 593D」Happy Tree Party

题目链接：Codeforces 593D

今天是 Bogdan 的生日，他的母亲送给他一棵有 $n​$ 个节点的树，每条边上有一个数字 $x_i​$。有 $m​$ 个客人参加了 Bogdan 的生日排队。第 $i​$ 个客人到达后，他会进行如下 $2​$ 种操作中的恰好一种：

1. 选择一个数字 $y_i$ 和两个节点 $a_i,b_i$。接下来他沿着 $a_i$ 到 $b_i$ 的最短路径行走。每经过一条边 $j$，他就把当前的数字 $y_i$ 替换成 $\left\lfloor\frac{y_i}{x_j}\right\rfloor$。最后求出 $y_i$ 的值。
2. 选择一条边 $p_i$，将这条边上的值 $x_{p_i}$ 替换成 $c_i$。其中 $c_i<x_{p_i}$。

由于 Bogdan 非常好客，他希望编写一个程序执行所有的操作，并对每个操作 $1$ 求出其结果 $y_i$ 的值。

数据范围：$2\le n \le 2\times 10^5$，$1\le m\le 2\times 10^5$，$1\le x_i,y_i\le 10^{18}$，$1\le c_i<x_{p_i}$。