#2818. 有向图点权值更新(简单图)
有向图点权值更新(简单图)
题目描述
给定一个有向图,图中有 个顶点, 条边,编号从 到 。初始时,每个顶点的点权值均为 。接下来,会进行 次操作,每次操作指定一个顶点 和一个正整数 ,表示将顶点 指向的所有顶点(除了自己)
的点权值都增加 。在所有操作完成后,求出每个顶点的点权值。
输入格式
- 第一行包含三个整数 、 和 ,分别表示顶点数、操作数和有向边数。
- 接下来 行,每行包含两个整数 和 ,表示一条有向边,其中 是边的起点, 是边的终点。
- 接下来 行,每行包含两个整数 和 ,表示一次操作,其中 是操作的顶点编号, 是增加的点权值。
输出格式
输出一行,包含 个整数,分别表示每个顶点的点权值,用空格隔开。
样例
样例输入
4 3 3
1 2
1 3
2 4
1 2
2 3
3 4
样例输出
0 2 2 3
解释
- 初始时,所有顶点的点权值为 。
- 第一次操作,顶点 的出边指向顶点 和 ,顶点 和 的点权值分别增加 。
- 第二次操作,顶点 的出边指向顶点 ,顶点 的点权值增加 。
- 第三次操作,顶点 的出边指向顶点没有,不需要增加。
- 最终,顶点 的点权值为 ,顶点 的点权值为 ,顶点 的点权值为 ,顶点 的点权值为 。
数据范围
- 每个顶点的出边数量不超过
简单图(没有重边和自环)