rt，只有12pts的splay

5个点AC，其余35个点全部TLE，经过测试发现下面的样例在insert函数中会进入死循环

昨天调了一个下午还是没调出qwq

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+100;
const ll inf=1e18;
int n,m;
ll L[N];//领导力 
int b[N],c[N];//上级/薪水 
int rt[N];//根节点 
ll res=0;//最终答案 
vector<int> son[N];//存每个节点的孩子 
int num[N];//孩子的数量 
struct Tree{
	int ch[2],sz,sum,fa,v;
	void init(int _v,int _fa){
		v=_v,fa=_fa;
		sz=1;
	}
}tr[N];//用struct存平衡树 
void pushup(int u){
	tr[u].sz=tr[tr[u].ch[0]].sz+tr[tr[u].ch[1]].sz+1;
	tr[u].sum=tr[tr[u].ch[0]].sum+tr[tr[u].ch[1]].sum+tr[u].v;
}//向上更新节点的size和维护的区间和sum 
void rotate(int x){
	int y=tr[x].fa,z=tr[y].fa;
	bool k=tr[y].ch[1]==x; 
	tr[z].ch[tr[z].ch[1]==y]=x;tr[x].fa=z;
	tr[y].ch[k]=tr[x].ch[k^1],tr[tr[x].ch[k^1]].fa=y;
	tr[x].ch[k^1]=y,tr[y].fa=x;
	pushup(y),pushup(x);
}//正常的rotate 
void splay(int &root,int x,int k){
	while(tr[x].fa!=k){
		int y=tr[x].fa,z=tr[y].fa;
		if(z!=k){
			if((tr[z].ch[1]==y)^(tr[y].ch[1]==x))rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	if(!k)root=x;
}//将x旋转到以root为根的splay中节点k的下方 
void insert(int &root,int v,int id){
	int u=root,fa=0;
	while(u)fa=u,u=tr[u].ch[v>tr[u].v];
	u=id;
	if(fa)tr[fa].ch[v>tr[fa].v]=u;
	tr[u].init(v,fa);
	splay(root,u,0); 
}//向以root为节点的splay中加入权值为v,编号为id的节点 
void build(int u){
	rt[u]=u;
	tr[u].init(c[u],0);
}//单独建立一棵以u为根节点的splay
void merge(int &root,int u){
	//cout<<"merge"; 
	int l=tr[u].ch[0],r=tr[u].ch[1];
	if(l)merge(root,l);
	insert(root,tr[u].v,u);
	if(r)merge(root,r); 
}//对u进行dfs，将u的子树的节点都insert到以root为根的splay中 
int get_k(int &root,int k){
	int u=root;
	while(true){
		if(tr[tr[u].ch[0]].sz>=k)u=tr[u].ch[0];
		else if(tr[tr[u].ch[0]].sz+1==k)return u;
		else k-=tr[tr[u].ch[0]].sz+1,u=tr[u].ch[1];
	}
}//找到一棵splay第k小的节点 
ll query(int &root,int r){
	if(r==tr[root].sz)return tr[root].sum;
	r=get_k(root,r+1);
	splay(root,r,0);
	return tr[tr[root].ch[0]].sum;
}//查询前r大的权值之和 
void solve(int u){
	if(num[u]==0){
		build(u);
		res=max(res,L[u]);
		return;
	}//没有孩子节点就直接建立一棵单节点splay并更新答案 
	for(int i=0;i<num[u];i++)solve(son[u][i]);//递归求解每颗子树 
	int maxid=son[u][0];//按秩合并，选出节点数最大的子树 
	for(int i=1;i<num[u];i++)if(tr[rt[son[u][i]]].sz>tr[rt[maxid]].sz)maxid=son[u][i];
	rt[u]=rt[maxid];//将u的根节点改为maxid的根节点 
	insert(rt[u],c[u],u);//将u插入子树 
	for(int i=0;i<num[u];i++)if(son[u][i]!=maxid)merge(rt[u],rt[son[u][i]]);//将其他节点插入到子树中 
	int l=0,r=tr[rt[u]].sz;
	while(l<r){//二分 
		int mid=(l+r+1)>>1; 
		if(query(rt[u],mid)>m)r=mid-1;
		else l=mid;
	}//O(long^2n)查找答案，等到其他bug修好后再改成O(logn)的 
	res=max(res,r*L[u]);//更新答案 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>b[i]>>c[i]>>L[i];
	for(int i=2;i<=n;i++)son[b[i]].push_back(i),num[b[i]]++;//找到每个点的儿子 
	solve(1);
	cout<<res<<endl;
}
/*
小样例 
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

6

会TLE的数据 
100 1000000000
0 2 21970731
1 2 222398317
1 2 74179205
1 2 366800569
4 2 142701324
1 2 394729069
5 1 192544852
1 2 328363234
1 1 506128975
1 1 314621418
1 2 148256480
1 1 329029287
1 2 119329652
1 1 156297911
1 2 167336956
1 2 148648026
1 2 403555792
1 2 300192800
1 2 292834809
1 1 249849421
1 2 315170864
1 2 169602882
1 1 350433533
1 2 1000000000
1 1 314962630
1 1 127507666
1 2 173747117
1 2 80131080
1 2 40063463
1 1 633298965
1 1 158594318
1 1 174677173
1 2 152928419
1 1 137301528
1 2 109172207
1 2 152059221
1 2 162712507
1 2 282021161
1 2 113693927
1 1 364172862
1 1 149833547
1 1 402021114
1 1 157182846
1 1 123203557
1 2 192282506
1 2 469870152
1 2 263805993
1 2 287965903
1 1 259194291
1 1 337170467
1 2 183017053
1 1 374362263
1 2 132108510
29 1 395364373
1 2 214071623
1 2 138477441
1 1 210674172
1 2 280316392
12 2 563432777
1 1 269322162
1 2 411170215
1 2 162057402
1 2 579160840
1 1 217791219
1 2 87487179
1 1 247444621
1 2 170169935
1 2 107140877
1 2 174262598
39 2 136621434
1 1 240890787
1 1 225148738
1 2 636501005
1 1 300972077
1 1 374234088
65 2 146208251
1 2 144872293
1 2 85519853
1 1 82760639
1 2 295481486
1 1 163078974
1 2 257067374
1 2 207032157
1 1 572787211
1 2 244927943
1 2 152292741
1 1 254426685
1 1 434929774
32 2 112897396
81 1 109917552
1 1 396222660
1 2 95642602
1 1 133063862
1 2 281040879
1 1 118249747
95 2 126451178
1 2 439570738
15 2 229832022
1 2 166445877
1 2 167907978

2197073100


*/