@[Sort_s](/user/225285) 你把主函数的void去掉就行
by Dimly_dust @ 2020-07-17 16:50:51
不过会全部WA
by Dimly_dust @ 2020-07-17 16:51:08
@[Sort_s](/user/225285) 嗯，不过我是去掉void才不RE的
by Dimly_dust @ 2020-07-17 17:04:24
第二个点现在T了。。。
by Most_Goodlooking @ 2020-07-17 17:08:42
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Ltree{
long long val=0;
int number;
int start;
int lson=0;
int rson=0;
int dist=0;
long long add=0;
long long mul=1;
}ztree[1000005];
long long h[300005],a[300005],v[300005];int root[300005]={},dep[300005]={},died[300005]={},killed[300005],head[500005]={},edge[500005],nxt[500005]={},tot=0,ltot=0;
inline long long read(){
long long res=0;char c=getchar();bool p=0;
while(c<'0'||c>'9'){if(c=='-')p=1;c=getchar();};
while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+c-'0';c=getchar();};
return p?-res:res;
}
void add_(int a,int b){
nxt[++tot]=head[a];
head[a]=tot;
edge[tot]=b;
}
bool pushdown(int x){
if(ztree[x].mul!=1){
ztree[ztree[x].lson].mul*=ztree[x].mul;ztree[ztree[x].lson].add*=ztree[x].mul;ztree[ztree[x].lson].val*=ztree[x].mul;
ztree[ztree[x].rson].mul*=ztree[x].mul;ztree[ztree[x].rson].add*=ztree[x].mul;ztree[ztree[x].rson].val*=ztree[x].mul;
ztree[x].mul=1;
}
if(ztree[x].add){
ztree[ztree[x].lson].add+=ztree[x].add;ztree[ztree[x].lson].val+=ztree[x].add;
ztree[ztree[x].rson].add+=ztree[x].add;ztree[ztree[x].rson].val+=ztree[x].add;
ztree[x].add=0;
}return 1;
}
int formage(int x,int y){
if(!x||!y) return x+y;
if(ztree[x].val>ztree[y].val) swap(x,y);
pushdown(x);pushdown(y);
ztree[x].rson=formage(ztree[x].rson,y);
if(ztree[ztree[x].lson].dist<ztree[ztree[x].rson].dist) swap(ztree[x].lson,ztree[x].rson);
ztree[x].dist=ztree[ztree[x].rson].dist+1;
return x;
}
void dfs(int now){
for(int i=head[now];i;i=nxt[i]){
int to=edge[i];
dep[to]=dep[now]+1;
dfs(to);
root[now]=formage(root[now],root[to]);
}
while(root[now]&&pushdown(now)&&ztree[root[now]].val<h[now]){
pushdown(root[now]);
died[now]++;killed[ztree[root[now]].number]=dep[ztree[root[now]].start]-dep[now];
root[now]=formage(ztree[root[now]].lson,ztree[root[now]].rson);
}
if(now==1){
while(root[now]){
killed[ztree[root[now]].number]=dep[ztree[root[now]].start]-dep[now]+1;
root[now]=formage(ztree[root[now]].lson,ztree[root[now]].rson);
}
}else if(a[now]){
ztree[root[now]].mul*=v[now];ztree[root[now]].add*=v[now];ztree[root[now]].val*=v[now];
}
else{
ztree[root[now]].add+=v[now];ztree[root[now]].val+=v[now];
}return;
}
int main(){
int n=(int)read(),m=(int)read(),val;
for(int i=1;i<=n;i++) h[i]=read();
for(int i=2;i<=n;i++){
val=(int)read();a[i]=read();v[i]=read();
add_(val,i);
}
for(int i=1;i<=m;i++){
++ltot;
ztree[ltot].val=read();val=(int)read();
ztree[ltot].number=i;ztree[ltot].start=val;
root[val]=formage(root[val],ltot);
}dep[1]=0;dfs(1);
for(int i=1;i<=n;i++) cout<<died[i]<<endl;
for(int i=1;i<=m;i++) cout<<killed[i]<<endl;
return 0;
}
```
by Most_Goodlooking @ 2020-07-17 17:11:31
@[Sort_s](/user/225285) 嗯，我把代码发给你
by Dimly_dust @ 2020-07-17 18:16:27
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Ltree
{
long long val=0;
long long number;
long long start;
long long lson=0;
long long rson=0;
long long dist=0;
long long add=0;
long long mul=1;
} ztree[1000005];
long long h[300005],a[300005],v[300005],root[300005]= {},dep[300005]= {},died[300005]= {},killed[300005],head[500005]= {},edge[500005],nxt[500005]= {},tot=0,ltot=0;
void add_(long long a,long long b)
{
nxt[++tot]=head[a];
head[a]=tot;
edge[tot]=b;
}
bool pushdown(long long x)
{
if(ztree[x].mul!=1)
{
ztree[ztree[x].lson].mul*=ztree[x].mul;
ztree[ztree[x].lson].add*=ztree[x].mul;
ztree[ztree[x].lson].val*=ztree[x].mul;
ztree[ztree[x].rson].mul*=ztree[x].mul;
ztree[ztree[x].rson].add*=ztree[x].mul;
ztree[ztree[x].rson].val*=ztree[x].mul;
ztree[x].mul=1;
}
if(ztree[x].add)
{
ztree[ztree[x].lson].add+=ztree[x].add;
ztree[ztree[x].lson].val+=ztree[x].add;
ztree[ztree[x].rson].add+=ztree[x].add;
ztree[ztree[x].rson].val+=ztree[x].add;
ztree[x].add=0;
}
return 1;
}
long long formage(long long x,long long y)
{
if(!x||!y) return x+y;
if(ztree[x].val>ztree[y].val) swap(x,y);
pushdown(x);
pushdown(y);
ztree[x].rson=formage(ztree[x].rson,y);
if(ztree[ztree[x].lson].dist<ztree[ztree[x].rson].dist) swap(ztree[x].lson,ztree[x].rson);
ztree[x].dist=ztree[ztree[x].rson].dist+1;
return x;
}
void dfs(long long now)
{
for(int i=head[now]; i; i=nxt[i])
{
long long to=edge[i];
dep[to]=dep[now]+1;
dfs(to);
root[now]=formage(root[now],root[to]);
}
while(root[now]&&pushdown(now)&&ztree[root[now]].val<h[now])
{
pushdown(root[now]);
died[now]++;
killed[ztree[root[now]].number]=dep[ztree[root[now]].start]-dep[now];
root[now]=formage(ztree[root[now]].lson,ztree[root[now]].rson);
}
if(now==1)
{
while(root[now])
{
killed[ztree[root[now]].number]=dep[ztree[root[now]].start]-dep[now]+1;
root[now]=formage(ztree[root[now]].lson,ztree[root[now]].rson);
}
}
else if(a[now])
{
ztree[root[now]].mul*=v[now];
ztree[root[now]].add*=v[now];
ztree[root[now]].val*=v[now];
}
else
{
ztree[root[now]].add+=v[now];
ztree[root[now]].val+=v[now];
}
return;
}
int main(void)
{
ios::sync_with_stdio(false);
long long n,m,val;
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>h[i];
for(int i=2; i<=n; i++)
{
cin>>val>>a[i]>>v[i];
add_(val,i);
}
for(int i=1; i<=m; i++)
{
++ltot;
cin>>ztree[ltot].val>>val;
ztree[ltot].number=i;
ztree[ltot].start=val;
root[val]=formage(root[val],ltot);
}
dep[1]=0;
dfs(1);
for(int i=1; i<=n; i++) cout<<died[i]<<endl;
for(int i=1; i<=m; i++) cout<<killed[i]<<endl;
return 0;
}
```
by Dimly_dust @ 2020-07-17 18:17:28
哦，你是没加O2吧，这种题一般都要加的
by Dimly_dust @ 2020-07-17 18:18:18