题意

给定一棵 $n$ 个节点的树，每个点有点权。你可以做任意次操作，每次操作可以让一个点的点权 $v_x\to v_{fa_x}+v_{c_x}-v_x$，其中 $fa_x$ 表示 $x$ 的父亲，$c_x$ 表示 $x$ 的任意一个儿子。

问最后所有节点的点权和最大为多少，若可以无限大则输出 +inf。

题解

首先发现一个结论：对于一个可以操作的节点，如果它有两个儿子权值不同，则可以让这个点无限增长，具体就是轮流使用两个儿子进行操作。

再考虑部分分中的链：对于一条链，这个操作的意义就是交换差分数组中相邻的两项。那么只需要求出差分数组并排序即可。

至此，这道题的做法已经清晰可见了，对于根的每棵子树都做一遍如下操作即可：

• 从根向下找到第一个有多个儿子的节点，设为 $x$。
• 对于 $x$ 的子树进行遍历。
  • 若一个点可以操作且有两个儿子权值不同，输出 +inf。
  • 若一个点 $i$ 可以操作使得 $v_i$ 改变（即 $v_{fa_i}+v_{c_i}\neq 2v_i$），并且 $fa_i$ 有多个儿子，在修改 $i$ 之后 $fa_i$ 就会有两个儿子权值不同，因此这种情况输出 +inf。
• 若 $x$ 有一个儿子有儿子，并且从根到 $x$ 的这条链上存在一个点 $i$ 的点权可以改变（即 $v_{fa_i}+v_{c_i}\neq 2v_i$），那么就可以从 $i$ 一路修改到 $x$ 的这个儿子，然后输出 +inf。

代码

最低版本要求为C++17

// Problem: [JSOI2010] 蔬菜庆典
// Made by: Acc_Robin
#include<vector>
#include<numeric>
#include<iostream>
#include<algorithm>
using namespace std;
enum{N=200009};
vector<int>G[N];
using ll=long long;
int ct;
auto wk=[](){
 int n,i,x,u,*h,*t,p;
 if(cin>>n,!n)exit(0);
 ++ct;
 vector<ll>v(n+1);
 vector<int>f(n+1),q(n+1);
 for(i=0;i<=n;++i)G[i].clear();
 for(i=1;i<=n;++i){
  cin>>x>>v[i],f[i]=~x?x:0;
  G[f[i]].emplace_back(i);
 }
 for(int&s:G[1]){
  vector w={1};
  for(p=0,x=s;G[x].size()==1;){
   p|=v[f[x]]+v[G[x][0]]!=v[x]*2;
   w.emplace_back(x),x=G[x][0];
  }
  if(w.emplace_back(x),G[x].size()){
   p|=v[f[x]]+v[G[x][0]]!=v[x]*2;
   w.emplace_back(G[x][0]);
  }
  for(h=q.data(),*(t=h+1)=x;h<t;){
   for(u=*++h;int&v:G[u])*++t=v;
   for(i=1;i<G[u].size();++i)
    if(v[G[u][i]]!=v[G[u][i-1]])
     return cout<<"+inf\n",0;
   if(u==x)continue;
   if(G[u].size())
    if(p||v[f[u]]+v[G[u][0]]!=2*v[u])
     return cout<<"+inf\n",0;
  }
  vector g(w.size(),0ll);
  for(g[0]=v[1],i=1;i<w.size();++i)
   g[i]=v[w[i]]-v[w[i-1]];
  sort(begin(g)+1,end(g),greater<>());
  partial_sum(begin(g),end(g),begin(g));
  for(i=0;i<g.size();++i)v[w[i]]=g[i];
 }
 cout<<accumulate(begin(v),end(v),0ll)<<'\n';
 return 0;
};
int main(){
 for(;;)wk();
}