首先，我们发现角色的攻击力始终没有发生变化，因此击杀所有怪物消耗的时间均相同。
令在第 $i$ 只怪物的位置的受击次数为 $y_i=\left(\left\lfloor\frac{h}{X-d}\right\rfloor-1\right)$。因此，我们可以在预处理时就受到 $a_iy_i$ 点伤害，然后在走到这个点时恢复 $y_i\times$ 当前防御力的生命。

这样，就相当于分成了两类点：

  • 蓝宝石：增加 $1$ 点防御力；
  • 战斗：恢复 $y_i\times$ 当前防御力的生命。

可以发现，我们要尽量先走蓝宝石，于是想到贪心。
但是正常直接贪心会产生一个问题，cmp 函数写不出，因此，应该使用类似 AGC023F 的方法，使用每次把最优的那个点连接到父亲的写法。

此时 cmp 函数就是临项交换，$x_1(y_1+y_2)+x_2y_2<x_2(y_1+y_2)+x_1y_1$，即 $x_1y_2<x_2y_1$。

但是 $x_i=y_i=0$ 的点会破坏全序关系，需要特判一下。

#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
using venti=__int128_t;
mt19937_64 rng(random_device{}());
constexpr int N=2e5+7;
int n,X,fa[N],dsu[N];
loli c[N][2];
basic_string<int>g[N];
int find(int x){
	if(x==dsu[x])return x;
	return dsu[x]=find(dsu[x]);
}
struct node{
	int id;loli c0,c1;
	friend bool operator<(const node&x,const node&y){
		return venti(x.c0)*y.c1<venti(y.c0)*x.c1;
	}
};
void dfs(int u){
	for(int v:g[u])if(v!=fa[u])
		fa[v]=u,dfs(v);
}
priority_queue<node>q;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>X;
	for(int i=1,u,v;i<n;i++)cin>>u>>v,g[u]+=v,g[v]+=u;
	for(int i=1;i<=n;i++)dsu[i]=i;
	venti ans=0;
	for(int i=2,op,a,h,d;i<=n;i++){
		cin>>op;
		if(op==1)c[i][0]=1;
		else{
			cin>>a>>d>>h;
			c[i][1]=(h-1)/(X-d);
			ans-=c[i][1]*a;
		}
	}
	dfs(1);
	for(int i=2;i<=n;i++)if(c[i][0]||c[i][1])
		q.emplace(i,c[i][0],c[i][1]);
	while(!q.empty()){
		auto[u,c0,c1]=q.top();q.pop();
		u=find(u);
		if(c[u][0]!=c0||c[u][1]!=c1)continue;
		int v=find(fa[u]);
		ans+=venti(c[v][0])*c[u][1];
		c[v][0]+=c[u][0];
		c[v][1]+=c[u][1];
		dsu[u]=v;
		if(v>1)q.emplace(v,c[v][0],c[v][1]);
	}
	string tmp;
	if(ans<0)cout<<'-',ans=-ans;
	do tmp+='0'+ans%10,ans/=10;while(ans);
	reverse(all(tmp));
	cout<<tmp;
	return 0;
}