Gorgeous Sequence
操作
- 区间与 x x x取 m i n \rm min min
- 查询区间最大值
- 查询区间和
比较暴力的线段树维护区间
Max: 区间最大值sub_max: 严格小于最大值的区间次大值cnt_max: 最大值个数sum: 区间和tag: 区间取 m i n \rm min min的标记记录值
考虑取 m i n \rm min min操作走到一个区间上
-
最大值都不大于取 m i n \rm min min的对象，说明操作没用，
return -
如果小于最大值却严格大于次大值
此时的操作相当于区间加，打标记
sum-=(Max-x)*max_cnt;Max=x -
否则暴力走两边
利用势能分析时间复杂度
- 定义势能函数为 ∑ i d i \sum_i d_i ∑i?di?， i i i是线段树上的节点， d i d_i di?是这个节点对应的区间中，互不相同的元素个数
- 初始时，显然势能是 O ( n l o g n ) O(\rm nlogn) O(nlogn)
- 暴力对长度为 n n n的区间做 m i n \rm min min，消耗的时间是 O ( n ) O(n) O(n)，势能也会减少 O ( n ) O(n) O(n)
#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
#define maxn 1000005
#define lson num << 1
#define rson num << 1 | 1
struct node {
int Max, sub_max, cnt_max, sum, tag;
}t[maxn << 2];
int a[maxn];
void pushup( int num ) {
if( t[lson].Max > t[rson].Max ) {
t[num].Max = t[lson].Max;
t[num].cnt_max = t[lson].cnt_max;
t[num].sub_max = max( t[lson].sub_max, t[rson].Max );
}
else if( t[lson].Max < t[rson].Max ) {
t[num].Max = t[rson].Max;
t[num].cnt_max = t[rson].cnt_max;
t[num].sub_max = max( t[rson].sub_max, t[lson].Max );
}
else {
t[num].Max = t[lson].Max;
t[num].cnt_max = t[lson].cnt_max + t[rson].cnt_max;
t[num].sub_max = max( t[lson].sub_max, t[rson].sub_max );
}
t[num].sum = t[lson].sum + t[rson].sum;
}
void build( int num, int l, int r ) {
t[num].Max = t[num].sub_max = t[num].cnt_max = t[num].sum = 0, t[num].tag = -1;
if( l == r ) {
t[num].Max = t[num].sum = a[l];
t[num].sub_max = -1;
t[num].cnt_max = 1;
return;
}
int mid = l + r >> 1;
build( lson, l, mid );
build( rson, mid + 1, r );
pushup( num );
}
void pushdown( int num ) {
if( ! ~ t[num].tag ) return;
int val = t[num].tag;
if( t[lson].Max > val ) {
t[lson].sum -= ( t[lson].Max - val ) * t[lson].cnt_max;
t[lson].Max = t[lson].tag = val;
}
if( t[rson].Max > val ) {
t[rson].sum -= ( t[rson].Max - val ) * t[rson].cnt_max;
t[rson].Max = t[rson].tag = val;
}
t[num].tag = -1;
}
void modify( int num, int l, int r, int L, int R, int val ) {
if( R < l or r < L or t[num].Max <= val ) return;
if( L <= l and r <= R and t[num].sub_max < val ) {
t[num].sum -= ( t[num].Max - val ) * t[num].cnt_max;
t[num].Max = t[num].tag = val;
return;
}
pushdown( num );
int mid = l + r >> 1;
modify( lson, l, mid, L, R, val );
modify( rson, mid + 1, r, L, R, val );
pushup( num );
}
int query_max( int num, int l, int r, int L, int R ) {
if( r < L or R < l ) return -1;
if( L <= l and r <= R ) return t[num].Max;
pushdown( num );
int mid = l + r >> 1;
return max( query_max( lson, l, mid, L, R ), query_max( rson, mid + 1, r, L, R ) );
}
int query_sum( int num, int l, int r, int L, int R ) {
if( r < L or R < l ) return 0;
if( L <= l and r <= R ) return t[num].sum;
pushdown( num );
int mid = l + r >> 1;
return query_sum( lson, l, mid, L, R ) + query_sum( rson, mid + 1, r, L, R );
}
signed main() {
int n, m, T, opt, l, r, x;
scanf( "%lld", &T );
while( T -- ) {
scanf( "%lld %lld", &n, &m );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
build( 1, 1, n );
while( m -- ) {
scanf( "%lld %lld %lld", &opt, &l, &r );
switch ( opt ) {
case 0 : { scanf( "%lld", &x ); modify( 1, 1, n, l, r, x );break; }
case 1 : { printf( "%lld\n", query_max( 1, 1, n, l, r ) ); break; }
case 2 : { printf( "%lld\n", query_sum( 1, 1, n, l, r ) ); break; }
}
}
}
return 0;
}
Tyvj 1518 CPU监控
操作
- 区间加
- 区间赋值
- 查询区间最大值
- 查询区间历史最大值
线段树维护
Max: 区间最大值Hmax: 区间历史最大值add: 区间加标记Hadd: 区间历史最大加标记tag: 区间赋值标记Htag: 区间历史最大赋值标记
假想不合并标记，每个节点上有一个队列（按照时间先进先出），放着所有曾经推过来的标记
下推标记时，将该节点上所有的标记推到两个儿子处，并清空队列
对于每个节点，每次有一个区间加add标记推来时，令Max←Max+add 然后Hmax←max(Hmax,Max)
设推来的加法标记分别为 a d d [ 1... k ] add[1...k] add[1...k]，其前缀和为 S [ 1... k ] S[1...k] S[1...k]
则打上第
i
i
i个标记之后，Max的值为Max+S[i]
所以，Hmax的值为
max
?
i
=
1
k
M
a
x
+
S
[
i
]
=
M
a
x
+
max
?
i
=
1
k
S
[
i
]
\max_{i=1}^k Max+S[i]=Max+\max_{i=1}^k S[i]
maxi=1k?Max+S[i]=Max+maxi=1k?S[i]
因此只需记录 max ? i = 1 k S [ i ] \max_{i=1}^k S[i] maxi=1k?S[i]，就能得知该标记队列对节点的影响
合并加法标记时简单求和，前
i
i
i个标记合并后恰好等于
S
[
i
]
S[i]
S[i]，那么
max
?
i
=
1
k
S
[
i
]
\max_{i=1}^k S[i]
maxi=1k?S[i]可以表述为标记的历史最大值Hadd
此题含有赋值操作，赋值操作优先级更高，做法略有不同
赋值一次相当于前面所有的加标记和当前最大值都会被改变
所以赋值的时候，先下放所有的加标记，然后清空（包括历史）
同时，在加标记的时候如果已经有了赋值标记，直接把加标记叠加在赋值标记上
同时记录赋值历史的最大值，其很有可能成为历史最大值
#include <cstdio>
#include <iostream>
using namespace std;
#define inf 1e18
#define maxn 100005
#define int long long
#define lson num << 1
#define rson num << 1 | 1
struct node {
int Max, Hmax, add, Hadd, tag, Htag;
}t[maxn << 2];
int a[maxn];
void build( int num, int l, int r ) {
t[num].Max = t[num].Hmax = t[num].tag = t[num].Htag = -inf;
t[num].add = t[num].Hadd = 0;
if( l == r ) { t[num].Max = t[num].Hmax = a[l]; return; }
int mid = ( l + r ) >> 1;
build( lson, l, mid );
build( rson, mid + 1, r );
t[num].Max = t[num].Hmax = max( t[lson].Max, t[rson].Max );
}
void pushup( int num ) {
t[num].Max = max( t[lson].Max, t[rson].Max );
t[num].Hmax = max( t[lson].Hmax, t[rson].Hmax );
}
void down( int num, int add, int Hadd ) {
if( t[num].Htag != -inf )
t[num].Htag = max( t[num].Htag, t[num].tag + Hadd ), t[num].tag += add;
else
t[num].Hadd = max( t[num].Hadd, t[num].add + Hadd ), t[num].add += add;
}
void pushdown( int num, int l, int r ) {
if( t[num].tag == -inf and ! t[num].add ) return;
t[num].Hmax = max( t[num].Hmax, max( t[num].Htag, t[num].Max + t[num].Hadd ) );
if( t[num].add ) {
t[num].Max += t[num].add;
if( l ^ r ) {
down( lson, t[num].add, t[num].Hadd );
down( rson, t[num].add, t[num].Hadd );
}
}
if( t[num].tag != -inf ) {
t[num].Max = t[num].tag;
if( l ^ r ) {
t[lson].tag = t[rson].tag = t[num].tag;
t[lson].Htag = max( t[lson].Htag, t[num].Htag );
t[rson].Htag = max( t[rson].Htag, t[num].Htag );
}
}
t[num].add = t[num].Hadd = 0;
t[num].tag = t[num].Htag = -inf;
}
void add( int num, int l, int r, int L, int R, int val ) {
pushdown( num, l, r );
if( R < l or r < L ) return;
if( L <= l and r <= R ) {
if( t[num].tag != -inf )
t[num].tag += val, t[num].Htag = max( t[num].Htag, t[num].tag );
else
t[num].add += val, t[num].Hadd = max( t[num].Hadd, t[num].add );
pushdown( num, l, r );
return;
}
pushdown( num, l, r );
int mid = ( l + r ) >> 1;
add( lson, l, mid, L, R, val );
add( rson, mid + 1, r, L, R, val );
pushup( num );
}
void modify( int num, int l, int r, int L, int R, int val ) {
pushdown( num, l, r );
if( R < l or r < L ) return;
if( L <= l and r <= R ) {
t[num].tag = val;
t[num].Htag = max( t[num].Htag, val );
pushdown( num, l, r );
return;
}
pushdown( num, l, r );
int mid = ( l + r ) >> 1;
modify( lson, l, mid, L, R, val );
modify( rson, mid + 1, r, L, R, val );
pushup( num );
}
int query_max( int num, int l, int r, int L, int R ) {
if( R < l or r < L ) return -inf;
pushdown( num, l, r );
if( L <= l and r <= R ) return t[num].Max;
int mid = ( l + r ) >> 1;
return max( query_max( lson, l, mid, L, R ), query_max( rson, mid + 1, r, L, R ) );
}
int queryHmax( int num, int l, int r, int L, int R ) {
if( R < l or r < L ) return -inf;
pushdown( num, l, r );
if( L <= l and r <= R ) return t[num].Hmax;
int mid = ( l + r ) >> 1;
return max( queryHmax( lson, l, mid, L, R ), queryHmax( rson, mid + 1, r, L, R ) );
}
signed main() {
int n, m, l, r, x; char opt[5];
scanf( "%lld", &n );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
build( 1, 1, n );
scanf( "%lld", &m );
while( m -- ) {
scanf( "%s %lld %lld", opt, &l, &r );
switch ( opt[0] ) {
case 'Q' : { printf( "%lld\n", query_max( 1, 1, n, l, r ) ); break; }
case 'A' : { printf( "%lld\n", queryHmax( 1, 1, n, l, r ) ); break; }
case 'P' : { scanf( "%lld", &x ); add( 1, 1, n, l, r, x ); break; }
case 'C' : { scanf( "%lld", &x ); modify( 1, 1, n, l, r, x );break; }
}
}
return 0;
}
【清华集训2015】V
整那么高大上的物理电阻屁用没有
操作
- 区间加
- 区间减
- 区间赋值
- 查询单点值
- 查询单点历史最大值
这题很巧的转化将多个操作合并成了一种形式
将标记改写成(a,b)形式，标记对值的贡献转移形式改写成x←max(x+a,b)
- 区间加：
(val,-inf) - 区间减：
(-val,-inf) - 区间赋值：
(-inf,val)
标记的合并可以推出来，因为加法对取最大值满足分配率
- 假设原来的标记为
(a1,b1)，新来标记为(a2,b2) - max ? ( x + a 1 , b 1 ) ← ( a 2 , b 2 ) ? max ? ( max ? ( x + a 1 , b 1 ) + a 2 , b 2 ) ? max ? ( max ? ( x + a 1 + a 2 , b 1 + a 2 ) , b 2 ) \max(x+a_1,b_1)\leftarrow (a_2,b_2)\Rightarrow \max\Big(\max(x+a_1,b_1)+a_2,b_2\Big)\Rightarrow \max\Big(\max(x+a_1+a_2,b_1+a_2),b_2\Big) max(x+a1?,b1?)←(a2?,b2?)?max(max(x+a1?,b1?)+a2?,b2?)?max(max(x+a1?+a2?,b1?+a2?),b2?)
- 新来标记合并最后即为 x ← max ? ( x + a 1 + a 2 , max ? ( a 2 + b 1 , b 2 ) ) x\leftarrow \max\Big(x+a_1+a_2,\max(a_2+b_1,b_2)\Big) x←max(x+a1?+a2?,max(a2?+b1?,b2?))
考虑当前最大值的更新
两个标记取 m a x \rm max max相当于两个分段一次函数取 m a x \rm max max
m a x ( ( a 1 , b 1 ) , ( a 2 , b 2 ) ) = ( m a x ( a 1 , a 2 ) , m a x ( b 1 , b 2 ) ) \rm max\Big((a_1,b_1),(a_2,b_2))=(max(a_1,a_2),max(b_1,b_2)\Big) max((a1?,b1?),(a2?,b2?))=(max(a1?,a2?),max(b1?,b2?))
再考虑历史最大值的更新
(a0,b0)表示当前，(a1,b1)表示历史最大值，(c0,d0)表示传递点当前，(c1,d1)表示传递点历史最大
合并(a0,b0)和(c0,d0)：
(
a
0
+
c
0
,
max
?
(
b
0
+
c
0
,
d
0
)
)
\Big(a_0+c_0,\max(b_0+c_0,d_0)\Big)
(a0?+c0?,max(b0?+c0?,d0?))
合并(a1,b1)和(c1,d1)，先把(c1,d1)作用在(a0,b0)上，
(
a
0
+
c
1
,
max
?
(
b
0
+
c
1
,
d
1
)
)
\Big(a_0+c_1,\max(b_0+c_1,d_1)\Big)
(a0?+c1?,max(b0?+c1?,d1?))
再和(a1,b1)取max：
(
max
?
(
a
1
,
a
0
+
c
1
)
,
max
?
(
b
1
,
b
0
+
c
1
,
d
1
)
)
\Big(\max(a_1,a_0+c_1),\max(b_1,b_0+c_1,d_1)\Big)
(max(a1?,a0?+c1?),max(b1?,b0?+c1?,d1?))
（a,b相当于儿子，c,d代表父亲的信息）
#include <cstdio>
#include <iostream>
using namespace std;
#define maxn 500005
#define int long long
#define lson num << 1
#define rson num << 1 | 1
struct node {
int a, b, maxa, maxb;
}t[maxn << 2];
int w[maxn];
const int inf = 1e18;
void build( int num, int l, int r ) {
t[num].a = t[num].maxa = 0;
t[num].b = t[num].maxb = -inf;
if( l == r ) return;
int mid = l + r >> 1;
build( lson, l, mid );
build( rson, mid + 1, r );
}
void pushdown( int num ) {
if( ! t[num].a and t[num].b == -inf ) return;
t[lson].maxa = max( t[lson].maxa, t[lson].a + t[num].maxa );
t[lson].maxb = max( t[lson].maxb, max( t[lson].b + t[num].maxa, t[num].maxb ) );
t[rson].maxa = max( t[rson].maxa, t[rson].a + t[num].maxa );
t[rson].maxb = max( t[rson].maxb, max( t[rson].b + t[num].maxa, t[num].maxb ) );
t[lson].a = max( t[lson].a + t[num].a, -inf );
t[lson].b = max( t[lson].b + t[num].a, t[num].b );
t[rson].a = max( t[rson].a + t[num].a, -inf );
t[rson].b = max( t[rson].b + t[num].a, t[num].b );
t[num].a = t[num].maxa = 0;
t[num].b = t[num].maxb = -inf;
}
void modify( int num, int l, int r, int L, int R, int a, int b ) {
if( r < L or R < l ) return;
if( L <= l and r <= R ) {
t[num].a = max( t[num].a + a, -inf );
t[num].b = max( t[num].b + a, b );
t[num].maxa = max( t[num].a, t[num].maxa );
t[num].maxb = max( t[num].b, t[num].maxb );
return;
}
pushdown( num );
int mid = l + r >> 1;
modify( lson, l, mid, L, R, a, b );
modify( rson, mid + 1, r, L, R, a, b );
}
int query( int num, int l, int r, int pos, int k ) {
if( l == r ) {
if( ! k ) return max( w[l] + t[num].a, t[num].b );
else return max( w[l] + t[num].maxa, t[num].maxb );
}
pushdown( num );
int mid = l + r >> 1;
if( pos <= mid ) return query( lson, l, mid, pos, k );
else return query( rson, mid + 1, r, pos, k );
}
signed main() {
int n, m;
scanf( "%lld %lld", &n, &m );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &w[i] );
build( 1, 1, n );
for( int i = 1, opt, l, r, x;i <= m;i ++ ) {
scanf( "%lld", &opt );
switch ( opt ) {
case 1 : { scanf( "%lld %lld %lld", &l, &r, &x ), modify( 1, 1, n, l, r, x, 0 ); break; }
case 2 : { scanf( "%lld %lld %lld", &l, &r, &x ), modify( 1, 1, n, l, r, -x, 0 ); break; }
case 3 : { scanf( "%lld %lld %lld", &l, &r, &x ), modify( 1, 1, n, l, r, -inf, x ); break; }
case 4 : { scanf( "%lld", &x ), printf( "%lld\n", query( 1, 1, n, x, 0 ) ); break; }
case 5 : { scanf( "%lld", &x ), printf( "%lld\n", query( 1, 1, n, x, 1 ) ); break; }
}
}
return 0;
}
Naive Operations
刚开始区间全为 0 0 0，每次区间只 + 1 +1 +1
记录区间的最小值，
当最小值为 0 0 0的时候，说明多叠加了一个 b i b_i bi?的倍数
答案增加 1 1 1，然后重新把最小值置位 b i b_i bi? （这俩操作要走到叶子节点后再实行）
否则就打上整体 ? 1 -1 ?1的标记
#include <cstdio>
#include <iostream>
using namespace std;
#define maxn 100005
#define int long long
#define lson num << 1
#define rson num << 1 | 1
struct node {
int sum, tag, Min;
}t[maxn << 2];
int b[maxn];
void build( int num, int l, int r ) {
t[num].tag = t[num].sum = 0;
if( l == r ) { t[num].Min = b[l]; return; }
int mid = l + r >> 1;
build( lson, l, mid );
build( rson, mid + 1, r );
t[num].Min = min( t[lson].Min, t[rson].Min );
}
void pushdown( int num ) {
if( ! t[num].tag ) return;
t[lson].tag += t[num].tag;
t[rson].tag += t[num].tag;
t[lson].Min -= t[num].tag;
t[rson].Min -= t[num].tag;
t[num].tag = 0;
}
void modify( int num, int l, int r, int L, int R ) {
if( R < l or r < L ) return;
if( L <= l and r <= R ) {
t[num].Min --;
if( t[num].Min ) { t[num].tag ++; return; }
else if( l == r ) { t[num].sum ++, t[num].Min = b[l]; return; }
}
pushdown( num );
int mid = l + r >> 1;
modify( lson, l, mid, L, R );
modify( rson, mid + 1, r, L, R );
t[num].sum = t[lson].sum + t[rson].sum;
t[num].Min = min( t[lson].Min, t[rson].Min );
}
int query( int num, int l, int r, int L, int R ) {
if( r < L or R < l ) return 0;
if( L <= l and r <= R ) return t[num].sum;
pushdown( num );
int mid = l + r >> 1;
return query( lson, l, mid, L, R ) + query( rson, mid + 1, r, L, R );
}
signed main() {
int n, Q, l, r; char opt[10];
while( ~ scanf( "%lld %lld", &n, &Q ) ) {
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &b[i] );
build( 1, 1, n );
for( int i = 1;i <= Q;i ++ ) {
scanf( "%s %d %d", opt, &l, &r );
if( opt[0] == 'a' ) modify( 1, 1, n, l, r );
else printf( "%lld\n", query( 1, 1, n, l, r ) );
}
}
return 0;
}
Picture
扫描线求矩阵周长模板题
从下往上扫描线扫，横线长度：现在这次总区间被覆盖的长度和上一次总区间被覆盖的长度之差的绝对值
而竖线长度为，区间的段数*2，乘以 2 2 2是因为一段区间左右各一条
e.g. 段数
c
n
t
cnt
cnt的计算
- 若区间[0,10]被
[1,2][4,5]覆盖，则cnt=2 - 若区间[0,10]被
[1,3][4,5]覆盖，则cnt=1（两区间刚好连在一起） - 若区间[0,10]被
[1,5][2,6]覆盖，则cnt=1（两区间连起来还是一段）
扫描线中的线段树的一个节点代表一个单位长度线段
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 200005
#define lson num << 1
#define rson num << 1 | 1
struct node {
int l, r, h, op;
node(){}
node( int L, int R, int H, int Op ) {
l = L, r = R, h = H, op = Op;
}
}E[maxn];
struct tree {
int l, r, len, cnt, tag, flag_l, flag_r;
}t[maxn << 2];
bool cmp( node x, node y ) { return x.h < y.h; }
void build( int num, int l, int r ) {
t[num].l = l, t[num].r = r;
t[num].len = t[num].cnt = t[num].tag = t[num].flag_l = t[num].flag_r = 0;
if( l == r ) return;
int mid = l + r >> 1;
build( lson, l, mid );
build( rson, mid + 1, r );
}
void pushup( int num ) {
if( t[num].tag ) {
t[num].len = t[num].r - t[num].l + 1;
t[num].cnt = t[num].flag_l = t[num].flag_r = 1;
}
else if( t[num].l == t[num].r )
t[num].len = t[num].cnt = t[num].flag_l = t[num].flag_r = 0;
else {
t[num].len = t[lson].len + t[rson].len;
t[num].cnt = t[lson].cnt + t[rson].cnt - ( t[lson].flag_r and t[rson].flag_l );
t[num].flag_l = t[lson].flag_l, t[num].flag_r = t[rson].flag_r;
}
}
void modify( int num, int l, int r, int val ) {
if( t[num].r < l or r < t[num].l ) return;
if( l <= t[num].l and t[num].r <= r ) {
t[num].tag += val;
pushup( num );
return;
}
modify( lson, l, r, val );
modify( rson, l, r, val );
pushup( num );
}
int Fabs( int x ) { return x < 0 ? -x : x; }
int main() {
int n, x1, y1, x2, y2;
while( ~ scanf( "%d", &n ) ) {
int L = 1e9, R = -1e9;
for( int i = 1;i <= n;i ++ ) {
scanf( "%d %d %d %d", &x1, &y1, &x2, &y2 );
E[i] = node( x1, x2, y1, 1 );
E[i + n] = node( x1, x2, y2, -1 );
L = min( L, x1 );
R = max( R, x2 );
}
n <<= 1; R --;
sort( E + 1, E + n + 1, cmp );
build( 1, L, R );
int ans = 0, lst = 0;
for( int i = 1;i <= n;i ++ ) {
modify( 1, E[i].l, E[i].r - 1, E[i].op );
ans += Fabs( t[1].len - lst ) + 2 * t[1].cnt * ( E[i + 1].h - E[i].h );
lst = t[1].len;
}
printf( "%d\n", ans );
}
return 0;
}
Walking Race
用两次栈模拟 d p dp dp求出以每个点为端点的最长路径
用线段树维护区间内的路径最大值/最小值
尺取法，双指针判断区间 [ l , r ] [l,r] [l,r]是否在 m m m限制内
#include <stack>
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define maxn 1000005
#define lson num << 1
#define rson num << 1 | 1
const int inf = 1e9;
int n, m;
bool vis[maxn];
int maxlen[maxn];
stack < int > sta;
vector < pair < int, int > > G[maxn];
struct node {
int fa, d, Max, id, sub_max, sub_id;
void clear( int f, int dis ) { fa = f, d = dis, Max = id = sub_max = sub_id = 0; }
}MS[maxn];
void dfs1() {
for( int i = 1;i <= n;i ++ ) vis[i] = 0;
sta.push( 1 ), MS[1].clear( 0, 0 );
while( ! sta.empty() ) {
int u = sta.top();
if( ! vis[u] )
for( int i = 0;i < G[u].size();i ++ ) {
int v = G[u][i].first, dis = G[u][i].second;
if( v == MS[u].fa ) continue;
else MS[v].clear( u, dis ), sta.push( v );
}
else {
sta.pop();
for( int i = 0;i < G[u].size();i ++ ) {
int v = G[u][i].first, dis = G[u][i].second;
int len = MS[v].Max + dis;
if( len > MS[u].Max ) {
MS[u].sub_max = MS[u].Max;
MS[u].sub_id = MS[u].id;
MS[u].Max = len;
MS[u].id = v;
}
else if( len > MS[u].sub_max ) {
MS[u].sub_max = len;
MS[u].sub_id = v;
}
}
}
vis[u] = 1;
}
}
void dfs2() {
sta.push( 1 );
while( ! sta.empty() ) {
int u = sta.top(); sta.pop();
for( int i = 0;i < G[u].size();i ++ ) {
int v = G[u][i].first;
if( v == MS[u].fa ) continue;
else sta.push( v );
}
maxlen[u] = MS[u].Max;
if( u == 1 ) continue;
else {
int fa = MS[u].fa, len;
if( MS[fa].id == u ) len = MS[fa].sub_max + MS[u].d;
else len = MS[fa].Max + MS[u].d;
maxlen[u] = max( maxlen[u], len );
if( len > MS[u].Max ) {
MS[u].sub_max = MS[u].Max;
MS[u].sub_id = MS[u].id;
MS[u].Max = len;
MS[u].id = fa;
}
else if( len > MS[u].sub_max ) {
MS[u].sub_max = len;
MS[u].sub_id = fa;
}
}
}
}
struct tree { int Min, Max; }t[maxn << 2];
void build( int num, int l, int r ) {
if( l == r ) { t[num].Min = t[num].Max = maxlen[l]; return; }
int mid = l + r >> 1;
build( lson, l, mid );
build( rson, mid + 1, r );
t[num].Max = max( t[lson].Max, t[rson].Max );
t[num].Min = min( t[lson].Min, t[rson].Min );
}
int query_min( int num, int l, int r, int L, int R ) {
if( r < L or R < l ) return inf;
if( L <= l and r <= R ) return t[num].Min;
int mid = l + r >> 1;
return min( query_min( lson, l, mid, L, R ), query_min( rson, mid + 1, r, L, R ) );
}
int query_max( int num, int l, int r, int L, int R ) {
if( r < L or R < l ) return -inf;
if( L <= l and r <= R ) return t[num].Max;
int mid = l + r >> 1;
return max( query_max( lson, l, mid, L, R ), query_max( rson, mid + 1, r, L, R ) );
}
int main() {
int l, r, minn, maxx;
while( ~ scanf( "%d %d", &n, &m ) ) {
for( int i = 1;i <= n;i ++ ) G[i].clear();
for( int i = 2, fa, d;i <= n;i ++ ) {
scanf( "%d %d", &fa, &d );
G[fa].push_back( make_pair( i, d ) );
}
dfs1(), dfs2(), build( 1, 1, n );
l = r = 1, minn = maxx = maxlen[1];
int ans = 0;
while( l <= r and r <= n ) {
if( maxx - minn <= m ) {
ans = max( ans, r - l + 1 );
r ++;
minn = min( minn, maxlen[r] );
maxx = max( maxx, maxlen[r] );
}
else {
l ++;
minn = query_min( 1, 1, n, l, r );
maxx = query_max( 1, 1, n, l, r );
}
if( ans > n - l ) break;
}
printf( "%d\n", ans );
}
return 0;
}