模拟赛考到的题，过来发个题解。顺便吐槽一下这题真水，应该放第二题。
解法
刚看到这题我以为是树形 dp，仔细看了看题，发现题中的要求很少，没有依赖关系，没有要求联通，没有后效性，所以考虑贪心。
因为每个节点放装饰的代价都为正数，所以装饰越少越好。我们先去满足一个节点子树的要求，再去看这个节点的要求。分两种情况处理。
-
一个节点 $i$ 的子树的装饰总和不少于 $d_i$，则本着不浪费的原则，我们不管这个节点。
-
一个节点 $i$ 的子树的装饰总和少于 $d_i$，设其节点中已经有了 $m$ 个装饰，则本着不浪费的原则，我们在节点 $i$ 的子树中找到 $c_i$ 最少的点放 $d_i - m$ 个装饰，这样可以最小化这个点极其祖先的花费。
根据以上两种情况，我们从根节点开始深度优先搜索，按顺序贪心就可以了。
代码
#define int long long
int n,d[100010],c[100010],root,ans,yet[100010];
struct edge
{
int to;
edge *next;
};
edge *head[100010];
inline void add(const int &x,const int &y)
{
edge *e=new edge;
e->to=y,e->next=head[x],head[x]=e;
}
inline void dfs(int pos,int fa)
{
for(edge *i=head[pos];i!=nullptr;i=i->next)
if(i->to!=fa) dfs(i->to,pos),c[pos]=min(c[pos],c[i->to]),yet[pos]+=yet[i->to];
if(yet[pos]<d[pos]) ans+=(d[pos]-yet[pos])*c[pos],yet[pos]=d[pos];
}
signed main()
{
read(n);
for(int i=1,fa;i<=n;i++)
{
read(fa),read(d[i]),read(c[i]);
if(fa==-1) root=i;
else add(fa,i),add(i,fa);
}
dfs(root,0),cout<<ans;
return 0;
}
