@[little_kongbai](/user/232205) 与左偏树定义有关，这种定义是让空节点dist=-1，外节点dist=0，其实不赋-1而是赋0也只是让所有的dist++，这个初始值赋不赋大概是不会影响什么的
by AbioAg @ 2023-06-24 15:30:02
@[AbioAg](/user/762264) 感谢回复！之前写左偏树的题就是默认赋值为0 但这道题不赋值为-1只有20pts 题解里面虽然有强调要赋值为-1但是没说为什么
by little_kongbai @ 2023-06-24 16:04:09
@[little_kongbai](/user/232205) 这么离谱吗，有无code
by AbioAg @ 2023-06-24 16:23:49
@[AbioAg](/user/762264) 第34行 有初始dis=-1
ac code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int n,m,fa[N],rt[N],h[N],a[N],v[N],s[N],c[N],dep[N],die[N],
lc[N],rc[N],dis[N],mul[N],add[N],ans[N];
void pd(int x){
int t=lc[x];
s[t]*=mul[x];
s[t]+=add[x];
mul[t]*=mul[x];
add[t]*=mul[x];
add[t]+=add[x];
t=rc[x];
s[t]*=mul[x];
s[t]+=add[x];
mul[t]*=mul[x];
add[t]*=mul[x];
add[t]+=add[x];
add[x]=0;mul[x]=1;
}
int merge(int x,int y){
if(!x||!y)return x^y;
if(s[x]>s[y])swap(x,y);
pd(x);pd(y);
rc[x]=merge(rc[x],y);
if(dis[rc[x]]>dis[lc[x]])swap(lc[x],rc[x]);
dis[x]=dis[rc[x]]+1;
return x;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",h+i);
dep[1]=1,dis[0]=-1;
for(int i=2;i<=n;i++){
scanf("%lld%lld%lld",fa+i,a+i,v+i);
dep[i]=dep[fa[i]]+1;
}
for(int i=1;i<=m;i++){
scanf("%lld%lld",s+i,c+i);
if(!rt[c[i]]) rt[c[i]]=i;
else rt[c[i]]=merge(rt[c[i]],i);
mul[i]=1;
}
for(int i=n;i;i--){
while(rt[i]&&s[rt[i]]<h[i]){
die[rt[i]]=i;
if(!lc[rt[i]])rt[i]=0;
else pd(rt[i]),rt[i]=merge(lc[rt[i]],rc[rt[i]]);
}
if(!rt[i])continue;
if(a[i]) s[rt[i]]*=v[i],mul[rt[i]]*=v[i],add[rt[i]]*=v[i];
else s[rt[i]]+=v[i],add[rt[i]]+=v[i];
pd(rt[i]);
if(!rt[fa[i]])rt[fa[i]]=rt[i];
else pd(rt[fa[i]]),rt[fa[i]]=merge(rt[i],rt[fa[i]]);
}
for(int i=1;i<=m;i++)ans[die[i]]++;
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
for(int i=1;i<=m;i++)printf("%lld\n",dep[c[i]]-dep[die[i]]);
return 0;
}
```
by little_kongbai @ 2023-06-24 16:29:33
20pts [https://www.luogu.com.cn/record/113260988](https://www.luogu.com.cn/record/113260988)
by little_kongbai @ 2023-06-24 16:30:20
@[little_kongbai](/user/232205) 你这个统计答案不太对劲吧，改成dfs试试呢
by AbioAg @ 2023-06-24 18:32:34
@[AbioAg](/user/762264) 这个答案统计参考的第一篇题解写的
by little_kongbai @ 2023-06-25 11:50:22
@[little_kongbai](/user/232205) 您试试这份，我改了下第五篇题解，On Line 55,初始化了dist[0]=1.14514，应该是能过
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define re register
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define int long long
int read() {
char cc = getchar(); int cn = 0, flus = 1;
while(cc < '0' || cc > '9') { if( cc == '-' ) flus = -flus; cc = getchar(); }
while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar();
return cn * flus;
}
const int N = 300000 + 5 ;
struct Tr {
int son[2], val, dis, fr, add, mul ;
} t[N];
struct E {
int to, next ;
} e[N * 2];
int n, m, cnt ;
int h[N], rt[N], a[N], v[N], head[N], s[N], dis[N], ans[N], num[N] ;
void add( int x, int y ) {
e[++ cnt] = (E){ y, head[x] }, head[x] = cnt ;
}
void col( int x, int ad, int mu ) {
if( !x ) return ;
t[x].val *= mu, t[x].val += ad ;
t[x].mul *= mu, t[x].add *= mu, t[x].add += ad ;
}
void pushup( int x ) {
col( ls(x), t[x].add, t[x].mul ) ;
col( rs(x), t[x].add, t[x].mul ) ;
t[x].add = 0, t[x].mul = 1 ;
}
int merge( int x, int y ) {
if( !x || !y ) return x + y ;
pushup(x), pushup(y) ;
if( t[x].val > t[y].val ) swap( x, y ) ;
rs(x) = merge( rs(x), y ) ;
if( t[rs(x)].dis > t[ls(x)].dis ) swap( ls(x), rs(x) ) ;
t[x].dis = t[rs(x)].dis + 1 ; return x ;
}
int Del( int x ) {
pushup(x); return merge( ls(x), rs(x) ) ;
}
void solve( int x ) {
while( t[rt[x]].val < h[x] && rt[x] ) {
ans[rt[x]] = dis[t[rt[x]].fr] - dis[x] ;
rt[x] = Del( rt[x] ), ++ num[x] ;
}
}
void input() {
n = read(), m = read() ; int x; t[0].dis = 1.14514 ;
rep( i, 1, n ) h[i] = read() ;
rep( i, 2, n ) x = read(), add( x, i ), a[i] = read(), v[i] = read() ;
rep( i, 1, m ) t[i].val = read(), t[i].fr = x = read(), t[x].mul = 1,
rt[x] = merge( rt[x], i ), t[i].dis = 1;
}
void dfs( int x, int f ) {
dis[x] = dis[f] + 1 ;
Next( i, x ) {
int v = e[i].to ;
dfs( v, x ), rt[x] = merge( rt[x], rt[v] ) ;
}
solve(x) ;
if( a[x] ) col( rt[x], 0, v[x] ) ;
else col( rt[x], v[x], 1 ) ;
}
void output() {
while( rt[1] ) ans[rt[1]] = dis[t[rt[1]].fr], rt[1] = Del( rt[1] );
rep( i, 1, n ) printf("%d\n", num[i] ) ;
rep( i, 1, n ) printf("%d\n", ans[i] ) ;
}
signed main()
{
input(), dfs( 1, 1 ), output() ;
return 0;
}
```
by AbioAg @ 2023-06-25 13:02:43
@[AbioAg](/user/762264) 好像for循环写法都要设dis[0]=-1 我教练那个dfs写法也没设
好奇怪啊
by little_kongbai @ 2023-06-25 13:22:46
@[little_kongbai](/user/232205) 那估计就是转移顺序的问题力，这个确实离谱
by AbioAg @ 2023-06-25 16:02:45