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;
}