作者:\(lyca\) 蒟蒻丁
为什么标签里有栈，但是没有单调栈的做法呢
这题需要我们求出每个骑士能爬到的最高的城池，但是怎样快速查找符合条件的城池呢，这个时候我们想到了单调栈。如果这些城池非常平凡，我们就可以直接比大小。但是每经过一个城池骑士的属性就会被改变，所以我们不能使用单调栈。但是转念一想，暴力算法是把骑士强行推上去，累加后比大小，那么我们能不能把城池推上去呢。答案是可以。我们可以先让骑士和城池一起爬到根节点，再用他们修改后的值比大小，证明如下：
考虑一个骑士和一个城池，城池的防御值是 \(y\) ,骑士走到该城池的战斗力是 \(x\) ，若城池也走到根节点后权值为 \(ay+b\) ，那么骑士走到根节点后权值就是 \(ax+b\) ，而题目中保证了乘数一定大于零，所以二者的相对大小是不会改变的，所以我们拿走到根节点的终值来比较是正确的。
于是我们可以得出一个做法，先用一次搜索求出每个城池和骑士的终值，再用单调栈来求出每个骑士能走到的最高点（这是模板了，在弹栈的时候记录一下修改值），就可以顺利解决本题。
有趣的是，出题人可能没有想过这种做法，城池的终值会爆 \(long long\) ，所以终值的记录需要 \(int 128\)，或者手写一些奇怪的压缩方式，需要注意的是不能直接取对数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=3e5+100;
__int128 h[N],f[N],tag1[N],tag2[N]={1,1},y;
ll n,m,head[N],cnt,st[N],ans1[N],ans2[N],top(1),pos[N],T[N],num[N];
ll a[N],dep[N],po;
bool pool[N];
vector<ll>vec[N];
struct star_platinum{
ll to,nxt,a,b;
}q[N<<1];
inline void add(ll u,ll v,ll a1,ll a2){
q[++cnt]={v,head[u],a1,a2},head[u]=cnt;
}
ll erf(__int128 x){
ll l=1,r=top,ans;
while(l<=r){
ll mid=(l+r)>>1;
if(f[st[mid]]>x)ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
void pre(ll x,ll fa){/////////处理终值
dep[x]=dep[fa]+1;
f[x]=a[x]*tag2[x]+tag1[x];
for(ll i=0;i<vec[x].size();i++)
h[vec[x][i]]=h[vec[x][i]]*tag2[x]+tag1[x];
for(ll i=head[x];i;i=q[i].nxt){
ll v=q[i].to;
if(q[i].a==1)tag2[v]=tag2[x]*q[i].b,tag1[v]=tag1[x];
if(q[i].a==0)
tag1[v]=tag1[x]+q[i].b*tag2[x],tag2[v]=tag2[x];
pre(v,x);
}
}
void dfs(ll x,ll fa){
T[x]=top;
po=erf(f[x]);
top=po;
pos[x]=st[top+1],num[x]=top+1;
st[++top]=x;
for(ll i=0;i<vec[x].size();i++){//////弹栈
y=h[vec[x][i]],po=erf(y);
ans1[st[po]]++,ans2[vec[x][i]]=dep[x]-dep[st[po]];
}
for(ll i=head[x];i;i=q[i].nxt){
ll v=q[i].to;
dfs(v,x);
}
st[num[x]]=pos[x];//////////回溯时还原栈
top=T[x];
}
int main(){
cin>>n>>m;
for(ll i=1;i<=n;i++)cin>>a[i];
for(ll i=2;i<=n;i++){
ll a1,a2,a3;
cin>>a1>>a2>>a3;
add(a1,i,a2,a3);
}
for(ll i=1;i<=m;i++){
ll a2,a1;
cin>>a2>>a1;
h[i]=a2;
vec[a1].push_back(i);
}
f[0]=3e18;
pre(1,0);
dfs(1,0);
for(ll i=1;i<=n;i++)printf("%lld\n",ans1[i]);
for(ll i=1;i<=m;i++)printf("%lld\n",ans2[i]);
return 0;
}