CF846E Chemistry in Berland 题解

题意：

cxy 是 Berland 大学化学系的研究生。她需要进行一个复杂的实验来撰写她的论文，但是 Berland 的实验室并没有包含这个实验所需要的所有材料。

幸运的是，化学法则允许物质之间的转化（不过 Berland 的化学与我们的不同），但是物质转化的规则有点奇怪。

Berland 化学家知道 $n$ 种材料，按照某种顺序编号为 $1, 2, \cdots, n$。每种材料都可以与其它一种材料互相转化。正式地，对任意 $2 \leq i \leq n$，都存在两个正整数 $x_i, k_i$ 表示一种合理的转化：$k_i \, \mathrm{kg}$ 的材料 $x_i$ 可以转化成 $1 \, \mathrm{kg}$ 的材料 $i$，而 $1 \, \mathrm{kg}$ 的材料 $i$ 只能变成 $1 \, \mathrm{kg}$ 的材料 $x_i$。

由于 Berland 的化学系统比较奇怪，因此转化只允许整数质量的材料。

对每个 $1 \leq i \leq n$，cxy 知道她的实验中需要 $a_i \, \mathrm{kg}$ 的材料 $i$，且实验室中只有 $b_i \, \mathrm{kg}$。她想知道，是否存在一种转化方案，使得最终实验能够顺利进行？

输入格式：

第一行包含一个正整数 $n~(n \leq 10^5)$，表示 Berland 化学家发现的材料的数量。

第二行包含 $n$ 个正整数 $b_1, b_2, \cdots, b_n~(b_i \leq 10^{12})$，表示 Berland 实验室的供应。

第三行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n~(a_i \leq 10^{12})$，表示实验所需（各种物质的）的质量。

接下来的 $n-1$ 行，每行包含两个正整数，其中第 $i$ 行的整数 $x_{i+1}, k_{i+1}~(1 \leq x_{i+1} \leq i, k_{i+1} \leq 10^9)$ 表示物质 $i+1$ 可以与物质 $x_{i+1}$ 相互转化，且转化系数为 $k_{i+1}$ （ $k_i$ 的含义见题目描述）。

输出格式：

输出 YES 如果实验可以进行，否则输出 NO。

注意到这是一棵树，因此考虑树形dp。

设 $f_i$ 表示 $i$ 所在子树ok之后，材料 $i$ 还能剩多少（负的说明欠了）。显然叶子结点有 $f_i = b_i - a_i$ 。

考虑转移。对于 $u$ 的儿子 $v \in \mathtt{son}(u)$ ，我们考虑以下几种情况：

$f_v \ge 0$ 。显然此时 $v$ 所在子树多出来的都可以给 $u$ 。f[u] += f[v]
$f_v < 0$ 。此时只能把 $u$ 的材料给 $v$ 。注意是 f[u] += k[v] * f[v] 。

最后只要看看是否有 $f_1>0$ 即可。~~然后你会发现这题其实是个贪心。~~

有趣的是这个算的过程中会爆 long long 。

解决办法，要么开 long double ，要么在小于 -INF 时直接让 f[u] = -INF 。

后者正确的原因在于 $f_i$ 增加的速度远低于其减少的速率，因此在 $f_i$ 极小时基本上是无解的。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,pos=1,f[N],a[N],k[N],b[N],limit[N],head[N];
struct Edge{ int u,v,next; } e[N];
void addEdge(int u,int v) { e[++pos]={u,v,head[u]}; head[u]=pos; }
void dfs(int u)
{
    f[u] = b[u] - a[u];
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; dfs(v);
        if(f[v] >= 0) f[u] += f[v];
        else (f[v] <= -limit[v]) ? (f[u] = -INF) : (f[u] += f[v] * k[v]);
        f[u] < -INF ? f[u] = -INF : 0;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> b[i];
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=2,fa; i<=n; i++)
    {
        cin >> fa >> k[i];
        addEdge(fa,i); limit[i] = INF / k[i];
    }
    dfs(1);
    cout << ((f[1] < 0) ? "NO\n" : "YES\n");
    return 0;
}