阅读量:0
[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription]
感谢伟大的洛谷。
[Solution] \color{blue}{\texttt{[Solution]}} [Solution]
显然，这题直接求解非常麻烦。
考虑一些技巧，我们发现答案是有单调性的：如果存在一种方法能使 a 1 a_{1} a1 变成 u u u，那么对于任意的 a 1 ≤ v < u a_{1} \leq v<u a1≤v<u，一定存在一种
方案能使 a 1 a_{1} a1 变成 v v v。
有单调性就有可二分性，于是我们考虑使用二分答案的方法把这道题从求解性问题变成判断性问题。
一个经验的事实是：判断性问题的难度一般比同性质的求解性问题小。
现在让我们思考给定一个 k k k，如何判定这个 k k k 是否可行。
树上的问题，一般情况下首先就要考虑求解的方向：即从根到叶还是从叶到根。
显然从叶到根方法太多，不便于考虑。所以我们从根到叶考虑。
要想把 a 1 a_{1} a1 变成 k k k，就需要对 1 1 1 的每一棵子树进行 ( k − a 1 ) (k-a_{1}) (k−a1) 次操作。
现在考虑 1 1 1 的子树 u u u：
- 如果 a u ≥ k − a 1 a_{u} \geq k-a_{1} au≥k−a1，那么对于 u u u 的每一棵子树 v v v，只需要进行 ( k − a 1 ) (k-a_{1}) (k−a1) 次操作（这不是对 u u u 在操作导致的，而是对 1 1 1 操作导致的）。
- 如果 a u < k − a 1 a_{u}<k-a_{1} au<k−a1，那么对 u u u 需要进行 ( k − a 1 − a u ) (k-a_{1}-a_{u}) (k−a1−au) 次操作，由于对 1 1 1 还需要 ( k − a 1 ) (k-a_{1}) (k−a1) 次操作，因此对 u u u 的每一棵子树 v v v，一共需要进行 ( k − a 1 ) + ( k − a 1 − a u ) (k-a_{1})+(k-a_{1}-a_{u}) (k−a1)+(k−a1−au) 次操作。
接下来的过程具有重复性，dfs 即可。
[code] \color{blue}{\text{[code]}} [code]
bool dfs(int u,int Fa,ll k){ if (k>1e17) return false; bool ret=true,lef=true; for(int i=h[u];i;i=e[i].nxt){ int v=e[i].to; if (v==Fa) continue; lef=false; if (a[v]>=k) ret&=dfs(v,u,k); else ret&=dfs(v,u,k+(k-a[v])); } if (lef) return a[u]>=k; else return ret; } bool check(ll mid){ return dfs(1,0,mid-a[1]); } void initdata(){ for(int i=1;i<=(n<<1);i++) e[i]=(edge){0,0}; for(int i=1;i<=n+1;i++) a[i]=h[i]=0; ecnt=0;l=r=0; } int main(){ T=read(); while (T--){ n=read(); initdata(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=2;i<=n;i++) add(read(),i); l=ans=a[1];r=1e11; while (l<=r){ ll mid=(l+r)>>1; if (check(mid)){ l=mid+1; ans=mid; } else r=mid-1; } printf("%lld\n",ans); } return 0; } read() 是快读，e 和 h 是链式前向星建的图 由于比较简单，代码就不给了 