I.V.UOJ#284. 快乐游戏鸡
我们来思考一下你游戏的过程：每次找到一个最浅的 (w_i) 大于当前死亡次数的位置 (i)，走到那儿；不断这样，直到下面两件事中有一件先发生：
- 你当前的死亡次数允许你一路走到终点。
- 你的死亡次数已经不小于 (w_i)，需要寻找新的 (i)。
然后我们来思考这一过程，发现如果将子树中所有节点按深度排序，只访问那些 (w_i) 是前缀最大值的节点一定构成一组最优解。而这明显可以用一个单调栈处理。
又因为我们要合并父亲与儿子的单调栈，就可以启发式合并做到 (O(nlog n)) 或是选择长链剖分做到 (O(n))。介于这里是长链剖分学习笔记，选择长链剖分。
现在来思考如何求解。设我们当前考虑了从 (x) 到 (y) 的路径。首先，”死亡次数允许一路走到终点“，等价于死亡次数到达路径最大值，设为 (z)。假设单调栈中元素是 ((dep_1,w_1),(dep_2,w_2),dots,(dep_k,w_k))，则我们显然只需要截出 (wleq z) 的一段前缀 (1sim p)，将这段前缀全部走完后，因为 (w_{p+1}>z)，所以我们只需不断走 (p+1) 直到死亡次数达到 (z) 即可。
找到前缀可以使用单调栈上二分。找到路径最大值可以树上倍增。
然后我们考虑计算总路径长度。其等于 (Big(sumlimits_{i=1}^p(w_i-w_{i-1})dep_i+(z-w_{p})dep_{p+1}Big)+Big(dep_y-dep_xBig)-zdep_x)。其中各部分间已经用大括号分割好了。
最前面那个括号中的 (sum) 显然不能 (O(n)) 遍历单调栈计算，须要预处理。但是单调栈只能处理从栈底出发的后缀和，不能处理从栈顶出发的前缀和。但注意到本题的信息具有可减性，于是直接维护后缀和，然后用栈顶值减去 (p+1) 位置的值即可。
单调栈为了能够二分须保证下标连续，所以使用了指针维护。时间复杂度 (O(nlog n))。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300100],fa[300100],dep[300100],dpt[300100],son[300100],anc[300100][20],st[300100][20],tot;
ll res[300100];
vector<int>v[300100];
vector<pair<int,int> >u[300100];
struct node{int a,d;ll sum;}p[300100],*h[300100],*t[300100],stk[300100],*tp;
void insert(int x,node y){//insert y into the array of x
node *&H=h[x],*&T=t[x];
while(H<=T&&H->a<=y.a)H++;//y ought to have a smaller d than all elements in x, so just pop.
if(H>T||H->d>y.d)y.sum=(H<=T?1ll*(H->a-y.a)*H->d+H->sum:0),*--H=y;
}
void merge(int x,int y){//merge the array of y into that of x.
node*&hx=h[x],*&tx=t[x],*&hy=h[y],*&ty=t[y];
tp=stk;while(hx<=tx&&hx->d<ty->d)*++tp=*hx++;//insert the can-be-deleted elements into an accessory array,leaving those must-saving elements
while(tp>stk&&hy<=ty)insert(x,ty->d>tp->d?*ty--:*tp--);//insert the one with greater d, to make the'insert'operation valid.
while(tp>stk)insert(x,*tp--);while(ty>=hy)insert(x,*ty--);//the same way like normal merging.
}
int doubling(int x,int y){
int ret=0;
for(int i=19;i>=0;i--)if(anc[y][i]&&dep[anc[y][i]]>dep[x])ret=max(ret,st[y][i]),y=anc[y][i];
return ret;
}
ll solve(int x,int y){
if(x==y)return 0;int z=doubling(x,y);
// printf("(%d,%d,%d)
",x,y,z);
if(h[x]->a>=z)return 1ll*(h[x]->d-dep[x])*z+dep[y]-dep[x];//just simply go to the first element of the array for z times.
node *l=h[x],*r=t[x],*mid;//the first elememt is inadequate, need to binary search for the proper one.
while(l<r)(mid=(l+(r-l)/2))->a>=z?r=mid:l=mid+1;
return 1ll*l->d*(z-l->a)-1ll*dep[x]*z+(h[x]->sum-l->sum)+1ll*h[x]->a*h[x]->d+dep[y]-dep[x];
}
void dfs(int x){
++tot;if(son[x])dfs(son[x]),h[x]=h[son[x]],t[x]=t[son[x]];else h[x]=p+tot,t[x]=h[x]-1;
for(auto y:v[x])if(y!=son[x])dfs(y),merge(x,y);
for(auto i:u[x])res[i.second]=solve(x,i.first);
insert(x,(node){a[x],dep[x],0});
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=2;i<=n;i++)scanf("%d",&fa[i]),dep[i]=dep[fa[i]]+1,v[fa[i]].push_back(i),anc[i][0]=fa[i],st[i][0]=a[fa[i]];
for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1],st[i][j]=max(st[i][j-1],st[anc[i][j-1]][j-1]);
dpt[0]=-1;for(int i=n;i>=2;i--){dpt[i]=dpt[son[i]]+1;if(dpt[i]>dpt[son[fa[i]]])son[fa[i]]=i;}
scanf("%d",&m);
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),u[x].push_back(make_pair(y,i));
dfs(1);
for(int i=1;i<=m;i++)printf("%lld
",res[i]);
return 0;
}