/* 树上斜率优化 一开始想的是构造出一个序列 转化成一般的dp但是可能被卡 扫把状的树的话可能变成n*n 其实可以直接在树上维护这个单调队列 dfs虽然搞得是一棵树,但是每次都是dfs到的都是一个序列 虽然题目说的是从节点到1号 但是我们从1到节点也是一样搞 关键是dfs回溯的时候怎么把改掉的序列改回去 比如当前是u 队列里面从hea到tai 我们搞到v1 搞v1的时候 会从队首扔掉几个斜率小的 到时回溯回来的时候 hea 和tai 是随着状态存到栈里的 问题不大 q不变不影响 但是 把v1扔进去的时候 会可能先把队尾扔几个 这就问题大了有点慌 因为我们后面要用到这些东西 倘若我们记下队尾的元素 搞完子树的事情再弄回去 便好了 */ #include<cstdio> #include<cstring> #include<iostream> #define maxn 100010 #define ll long long using namespace std; int T,n,p,num,head[maxn],q[maxn]; ll s[maxn],ans,f[maxn]; struct node{ int v,t,pre; }e[maxn*2]; void Add(int from,int to,int dis){ num++;e[num].v=to; e[num].t=dis; e[num].pre=head[from]; head[from]=num; } void dfs(int now,int from,ll dis){ s[now]=dis; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v;if(v==from)continue; dfs(v,now,dis+e[i].t); } } ll X(int i){ return s[i]; } ll Y(int i){ return f[i]+s[i]*s[i]; } ll Dx(int i,int j){ return X(i)-X(j); } ll Dy(int i,int j){ return Y(i)-Y(j); } void Dfs(int now,int from,int hea,int tai){ int pre=-1; if(now!=1){ while(hea+1<tai&&Dy(q[hea+2],q[hea+1])<=2*s[now]*Dx(q[hea+2],q[hea+1]))hea++; int j=q[hea+1];f[now]=min(f[now],f[j]+(s[now]-s[j])*(s[now]-s[j])+p); while(hea+1<tai&&Dy(now,q[tai])*Dx(q[tai],q[tai-1])<=Dy(q[tai],q[tai-1])*Dx(now,q[tai]))tai--; pre=q[++tai];q[tai]=now; } ans=max(ans,f[now]); for(int i=head[now];i;i=e[i].pre){ int v=e[i].v;if(v==from)continue; Dfs(v,now,hea,tai); } if(pre!=-1)q[tai]=pre; } int main(){ scanf("%d",&T); while(T--){ num=0;ans=0; memset(head,0,sizeof(head)); memset(q,0,sizeof(q)); scanf("%d%d",&n,&p); int u,v,t; for(int i=1;i<n;i++){ scanf("%d%d%d",&u,&v,&t); Add(u,v,t);Add(v,u,t); } dfs(1,0,0); for(int i=1;i<=n;i++) f[i]=s[i]*s[i]; Dfs(1,0,0,0); printf("%lld ",ans); } return 0; }