A6524. 「BalticOI 2013」管道 Pipes
编程题
省选/NOI-
知识点
题目描述
有 $n$ 个水库，$m$ 条管道。Jester 会在某些管道中间凿开一个洞，让水流出来或者用水泵把水打进去。保证这个流速是偶数。对于一条管道 $(u, v)$，如果在中间凿开了一个洞让水流出来，流速是 $\frac{2dm^3}s$，那么水库 $u$ 和 $v$ 失水速度为 $\frac{dm^3}s$。同理，如果往一条管道 $(u, v)$ 注水，流速为 $\frac{2pm^3}s$，那么 $u$ 和 $v$ 得到水的速度是 $\frac{pm^3}s$。
给定图的构造以及每个水库的水流的变化，问每条边的方案是否唯一。
给定图的构造以及每个水库的水流的变化，问每条边的方案是否唯一。
输入格式
第一行：水库数量 $n$，管道数量 $m$（$1 \le n \le 100 000, 1 \le m \le 500 000$）。
下面 $n$ 行：第 $i$ 个水库的变化速度 $c_i$（$-10^9 \le c_i \le 10^9$）。
接下来 $m$ 行：$(u, v)$，保证没有重边。
下面 $n$ 行：第 $i$ 个水库的变化速度 $c_i$（$-10^9 \le c_i \le 10^9$）。
接下来 $m$ 行：$(u, v)$，保证没有重边。
输出格式
如果方案唯一，输出方案，每行一个数 $x_i$（$-10^9 \le xi \le 10^9$）表示第 $i$ 条管道的流量变化。放水为负数，灌水为正数。否则输出
0。输入输出样例
输入 #1
4 3 -1 1 -3 1 1 2 1 3 1 4
输出 #1
2 -6 2
输入 #2
4 5 1 2 1 2 1 2 2 3 3 4 4 1 1 3
输出 #2
0
说明/提示
$1 \le N \le 10^5,$ $1 \le M \le 5\times 10^5,$ $−10^9 \le c_i \le 10^9$。
如果方案唯一，$−10^9 \le x_i \le 10^9$。
对于 $30\%$ 的测试数据，水库为树结构。
翻译来自 abcdabcd987。
如果方案唯一，$−10^9 \le x_i \le 10^9$。
对于 $30\%$ 的测试数据，水库为树结构。
翻译来自 abcdabcd987。