题意：以前，在神秘的大陆，有一个青蛙王国，由最年长的青蛙——长者统治着。这个王国由N座城市组成，从东到西编号。第一座城市是首都，座落在最东边。每一个城市，连接者几个或者没有连接几个西边的城市，并且只连接了一个东边的城市。每天，都有一些大新闻发生在一些城市。长者想尽快地知道。所以，青蛙新闻工作者的工作就是，跑得比其他青蛙都快。当有巨大新闻发生在某座城市的时候，这座城市的新闻工作者将会携带信息，跑向首都。当到达另一个城市的时候，他可以继续跑，也可停下来让其他的新闻工作者传输信息。这些新闻工作者由于太年轻并且简单，不能有效的跑很长的距离。结果，他们需要 L2的时间来跑一条长度为L的路径。除此之外，传达信息需要P的时间，是为了检查传达信息是否有误，因为信息的误差会使长者极度的生气。现在你高兴的收到一个任务：计算从所有城市发送信息到首都的所需的最长的时间。我想问公然膜蛤真的好？

解题思路：可以将图看成一个由1点为根的树，每个点到根结点为路径是唯一的。设dp[u]为u点传输信息到根节点的所需时间。a[u]为u点到根节点的距离。很明显，dp[u] = min{dp[k]+(sum[u]−sum[k])2+P | k是u的祖先)。用斜率优化优化DP转移即可。但是不同的点路径不同，所以这里还需要记录在这个点对于斜率优化的队列操作了什么，回溯离开这个点的时候，需要撤销这些操作，操作每个点有一个栈记录即可。对于从根节点转移吃出来，可以考虑单独转移，也可设置dp[1]=-P。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define MP(x, y) make_pair(x, y)
typedef long long LL;
const int N = 1e5+5;
struct fs{
    LL fz, fm;
    fs(){fz = 0, fm = 1;};
    fs(LL fz2, LL fm2) : fz(fz2) , fm(fm2) {
        if(fm < 0){
            fz = -fz;
            fm = -fm;
        }
    }
    bool operator <(const fs &rhs) const{
        return fz * rhs.fm < fm * rhs.fz;
    }
    bool operator <(const LL rhs) const{
        return *this < fs(rhs, 1LL);
    }
};
int p[N], cnt;
struct edge{
    int v, w, nxt;
    edge(){}
    edge(int v, int w, int nxt) : v(v), w(w), nxt(nxt) {}
}E[N*2];
void addedge(int u, int v, int w){
    E[cnt].v = v, E[cnt].w = w, E[cnt].nxt = p[u], p[u] = cnt++;
}
void init(){
    memset(p, -1, sizeof(p)); cnt = 0;
}
void getmax(LL &x, LL y){
    if(y > x) x = y;
}
int head, tail;
LL ans, que[N], dp[N], sum[N]; //sum维护前缀和
LL P;
LL sqr(LL x){
    return x * x;
}
int getDP(int i, int j){
    return dp[j] + P + sqr(sum[i] - sum[j]);
}
fs getxl(int j, int k){ //取斜率
    return fs(dp[j] + sqr(sum[j]) - dp[k] - sqr(sum[k]), 2 * (sum[j] - sum[k]));
}
void dfs(int u, int fa, int len){
    sum[u] = sum[fa] + len;
    //0 pop_front 2 pop_back 3 push_back
    stack <pair <int, int> > stk;
    if(u != 1){
        while(tail - head >= 2 && getxl(que[head], que[head+1]) < sum[u]) stk.push(MP(0, que[head++]));
        dp[u] = getDP(u, que[head]);
        //dp[u] = min(dp[u], sum[u] * sum[u]);
        while(tail - head >= 2 && getxl(que[tail-1], u) < getxl(que[tail-2], que[tail-1])) stk.push(MP(2, que[--tail]));
    }
    que[tail++] = u;
    stk.push(MP(3, u));
    getmax(ans, dp[u]);
    for(int i = p[u]; ~i; i = E[i].nxt){
        int v = E[i].v, w = E[i].w;
        if(v == fa) continue;
        dfs(v, u, w);
    }
    while(!stk.empty()){
        int op = stk.top().first;
        int v = stk.top().second;
        stk.pop();
        if(op == 0) que[--head] = v;
        else if(op == 2) que[tail++] = v;
        else if(op == 3) tail--;
        else head++;
    }
}
int main(){
    int T, n;
    scanf("%d", &T);
    while(T--){
        scanf("%d%lld", &n, &P);
        init();
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i < n; i++){
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        ans = -1;
        head = tail = 0;
        dp[1] = -P;
        dfs(1, 0, 0);
        printf("%lld\n", ans);
    }
    return 0;
}