网上写作真正能赚钱的网站/让顾客进店的100条方法

Description

小铭铭最近获得了一副新的桌游，游戏中需要用 m 个骑士攻占 n 个城池。

这 n 个城池用 1 到 n 的整数表示。除 1 号城池外，城池 i 会受到另一座城池 fi 的管辖，
其中 fi

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define inf 1000000000
#define mod 65537
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=300005;
int n,m,h[N],f[N],a[N],s[N],rt[N],c[N],dep[N];
int mul[N],add[N],ls[N],rs[N],dis[N],victory[N];
int ans[N],v[N],son[N],Head[N],ret[N],Next[N],tot;
queue<int>q;
inline void pushdown(int x)
{if (mul[x]==1&&add[x]==0) return;int l=ls[x],r=rs[x];if (l){s[l]=s[l]*mul[x]+add[x];mul[l]*=mul[x];add[l]=add[l]*mul[x]+add[x];}if (r){s[r]=s[r]*mul[x]+add[x];mul[r]*=mul[x];add[r]=add[r]*mul[x]+add[x];}mul[x]=1;add[x]=0;
}
int merge(int a,int b)
{if (!a||!b) return a+b;if (s[a]>s[b]) swap(a,b);pushdown(a);rs[a]=merge(rs[a],b);if (dis[ls[a]]<dis[rs[a]]) swap(ls[a],rs[a]);dis[a]=dis[rs[a]]+1;return a;
}
inline void ins(int u,int v)
{ret[++tot]=v;Next[tot]=Head[u];Head[u]=tot;
}
void dfs(int now)
{for (int i=Head[now];i;i=Next[i]){dep[ret[i]]=dep[now]+1;dfs(ret[i]);}
}
main()
{n=read();m=read();for (int i=1;i<=n;i++) h[i]=read();for (int i=2;i<=n;i++){f[i]=read();a[i]=read();v[i]=read();son[f[i]]++;ins(f[i],i);}dfs(1);for (int i=1;i<=m;i++){s[i]=read();c[i]=read();mul[i]=1;rt[c[i]]=merge(rt[c[i]],i);}for (int i=1;i<=n;i++) if (!son[i]) q.push(i);while (!q.empty()){int now=q.front();q.pop();while (rt[now]&&s[rt[now]]<h[now]){pushdown(rt[now]);victory[rt[now]]=dep[c[rt[now]]]-dep[now];rt[now]=merge(ls[rt[now]],rs[rt[now]]);ans[now]++;}if (a[now]) mul[rt[now]]*=v[now],add[rt[now]]*=v[now],s[rt[now]]*=v[now];else add[rt[now]]+=v[now],s[rt[now]]+=v[now];if (f[now]){rt[f[now]]=merge(rt[f[now]],rt[now]);son[f[now]]--;if (!son[f[now]]) q.push(f[now]);}}int now=1;while (rt[now]){pushdown(rt[now]);victory[rt[now]]=dep[c[rt[now]]]-dep[now]+1;rt[now]=merge(ls[rt[now]],rs[rt[now]]);}for (int i=1;i<=n;i++) printf("%lld\n",ans[i]);for (int i=1;i<=m;i++) printf("%lld\n",victory[i]);
}