#P6936. 有向无环图
有向无环图
题目描述
给定一张有 个点、 条边的有向无环图。每个点的点权初始为 。需要依次执行 次操作。
1 u x:将从点 能到达的所有点的点权设为 。2 u x:将从点 能到达的所有点的点权改为原点权与 的较小值。3 u:询问点 的当前点权。
点 本身也在它能到达的点集中。
输入格式
第一行三个正整数 。
接下来 行,每行两个整数 ,表示一条从 到 的有向边。
接下来 行,每行是上述三种操作之一。
输出格式
对每个 3 u 操作,输出一行一个整数表示答案。
数据范围
,点的编号在 到 之间,。原题时间限制 3 秒,内存限制 512 MB。
| 原题数据占比 | 附加限制 |
|---|---|
| 20% | |
| 另外 10% | 无操作 1 |
| 无操作 2,且 | |
| 另外 20% | 无操作 2 |