P12759 [POI 2018 R2] 转账 Transfers

翻译来自于 [LibreOJ](https://loj.ac/p/5067)。

**题目译自 [XXV Olimpiada Informatyczna — II etap](https://sio2.mimuw.edu.pl/c/oi25-2/dashboard/) [Przelewy](https://szkopul.edu.pl/problemset/problem/o4N9I1hFMnpCUm0sjmIEYx_2/statement/)** Bajtazar 和朋友们计划清算最近一起露营的费用。他们共有 $n$ 人，第 $i$ 人的银行账户初始余额为 $x_i$ 拜托币，结算后应为 $y_i$ 拜托币。 拜托尼亚的银行转账费用高昂，幸好银行推出了一项奇特的促销活动。每人可在银行系统内任意添加好友，关系对称：若 $A$ 将 $B$ 设为好友，则 $B$ 自动将 $A$ 设为好友，且无人可自设为好友。促销允许每人免费向所有好友同时转账 $1$ 拜托币，无次数限制。 朋友们构建了一个包含 $n-1$ 条好友关系的网络，确保任意两人直接或间接相连（即通过普通转账可实现任意两人间资金转移）。他们想知道，是否仅用促销的转账操作，就能通过此网络完成结算。银行允许账户余额为负。

第一行包含一个整数 $n$ $(n \geq 2)$，表示朋友人数，编号为 $1$ 至 $n$。 第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$ $(0 \leq x_i \leq W)$，表示初始余额。 第三行包含 $n$ 个整数 $y_1, y_2, \ldots, y_n$ $(0 \leq y_i \leq W)$，表示目标余额。 接下来的 $n-1$ 行定义好友关系，第 $i$ 行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i)$，表示编号为 $a_i$ 和 $b_i$ 的朋友互为好友。

第一行输出 `TAK` 或 `NIE`，表示是否仅用促销转账完成结算。 若为 `TAK`，第二行输出一个整数，表示所需的最少转账操作次数。

下表展示了一种用四次促销转账完成结算的方式，各行表示每次转账后的账户余额。 | 朋友编号 | $1$ | $2$ | $3$ | $4$ | $5$ | |:----------:|:-----:|:-----:|:-----:|:-----:|:-----:| | 初始余额 | $4$ | $3$ | $2$ | $1$ | $0$ | | $2$ 转账（至 $1,4$） | $5$ | $1$ | $2$ | $2$ | $0$ | | $5$ 转账（至 $1$） | $6$ | $1$ | $2$ | $2$ | $-1$ | | $2$ 再次转账（至 $1,4$） | $7$ | $-1$ | $2$ | $3$ | $-1$ | | $1$ 转账（至 $2,3,5$） | $4$ | $0$ | $3$ | $3$ | $0$ | **附加样例** 1. $n=3, x_1=1, x_2=x_3=y_1=y_2=y_3=0$，答案 `NIE`。 2. $n=1000$，好友网络为星形，答案 `TAK`。 3. $n=1000000$，好友网络为线形，答案 `TAK`。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 10, W \leq 5$ | $20$ | | $2$ | $n \leq 1000, W \leq 1000000$ | $30$ | | $3$ | $n \leq 1000000, W \leq 1000000$ | $50$ |