第 1 行包含2个非负整数 n,t，分别表示城市的个数和数据类型（其意义将在后面提到）。输入文件的第 2 到 n 行，每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v，分别表示城市 v 的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。请注意：输入不包含编号为 1 的SZ市，第 2 行到第 n 行分别描述的是城市 2 到城市 n。

输出包含 n-1 行，每行包含一个整数。其中第 v 行表示从城市 v+1 出发，到达SZ市最少的购票费用。同样请注意：输出不包含编号为 1 的SZ市。

对于所有测试数据，保证 0≤p_v≤10⁶，0≤q_v≤10¹²，1≤f_v<v；保证 0<s_v≤l_v≤2×10¹¹，且任意城市到SZ市的总路程长度不超过 2×10¹¹。

输入的 t 表示数据类型，0≤t<4，其中：

当 t=0 或 2 时，对输入的所有城市 v，都有 f_v=v-1，即所有城市构成一个以SZ市为终点的链；

当 t=0 或 1 时，对输入的所有城市 v，都有 l_v=2×10¹¹，即没有移动的距离限制，每个城市都能到达它的所有祖先；

当 t=3 时，数据没有特殊性质。

n=2×10^5

#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>using namespace std;#define LL long long inline LL read(){    LL x=0,f=1; char ch=getchar();    while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}    return x*f;}#define MAXN 200010  int N,T;LL l[MAXN],p[MAXN],q[MAXN];struct EdgeNode{    int next,to; LL dis;}edge[MAXN<<1];int cnt=1,head[MAXN];inline void AddEdge(int u,int v,LL w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].dis=w;}inline void InsertEdge(int u,int v,LL w) {AddEdge(u,v,w); AddEdge(v,u,w);} LL Dist[MAXN],dp[MAXN];int fa[MAXN];inline void DFS(int now,int last){    for (int i=head[now]; i; i=edge[i].next)        if (edge[i].to!=last) {            Dist[edge[i].to]=Dist[now]+edge[i].dis;            fa[edge[i].to]=now;            DFS(edge[i].to,now);        }} int size[MAXN],mx[MAXN],root,Sz,visit[MAXN];inline void Getroot(int now,int last){    size[now]=1,mx[now]=0;    for (int i=head[now]; i; i=edge[i].next)        if (edge[i].to!=last && !visit[edge[i].to]) {            Getroot(edge[i].to,now);            size[now]+=size[edge[i].to];            mx[now]=max(mx[now],size[edge[i].to]);        }    mx[now]=max(mx[now],Sz-size[now]);    if (mx[now]<mx[root]) root=now;} int o[MAXN],tot;inline bool cmp(int x,int y) {return Dist[x]-l[x]>Dist[y]-l[y];}inline void Dfs(int now,int last){    o[++tot]=now;    for (int i=head[now]; i; i=edge[i].next)        if (edge[i].to!=last && !visit[edge[i].to])            Dfs(edge[i].to,now);} inline double slope(int x,int y) {return (double)(dp[x]-dp[y])/(double)(Dist[x]-Dist[y]);} int stack[MAXN],top;double k[MAXN];inline void Insert(int x){    while (top>1 && slope(x,stack[top])>slope(stack[top],stack[top-1])) top--;    stack[++top]=x; k[top]=-slope(x,stack[top-1]);} inline void Divide(int x){     //  printf("Divide  %d  \n",x);         if (Sz<=1) return;    root=0; Getroot(x,0); int now=root;         for (int i=head[fa[now]]; i; i=edge[i].next)        if (edge[i].to==now && !visit[edge[i].to]) {            visit[now]=1;            Sz=size[x]-size[now];            Divide(x);            break;        }         for (int i=fa[now]; i!=fa[x]; i=fa[i])         if (Dist[now]-Dist[i]<=l[now])            dp[now]=min(dp[now],dp[i]+(Dist[now]-Dist[i])*p[now]+q[now]);         tot=0;         for (int i=head[now]; i; i=edge[i].next)        if (edge[i].to!=fa[now] && !visit[edge[i].to])            Dfs(edge[i].to,now);         sort(o+1,o+tot+1,cmp);         top=0;         for (int i=1,j=now; i<=tot; i++) {        for ( ; j!=fa[x] && Dist[j]>=Dist[o[i]]-l[o[i]]; j=fa[j]) Insert(j);        if (top==1) {            if (Dist[o[i]]-Dist[stack[top]]<=l[o[i]])                dp[o[i]]=min(dp[o[i]],dp[stack[top]]+(Dist[o[i]]-Dist[stack[top]])*p[o[i]]+q[o[i]]);        } else {            int ot=min(top,upper_bound(k+2,k+top+1,-p[o[i]])-k-1);            if (Dist[o[i]]-Dist[stack[ot]]<=l[o[i]])                dp[o[i]]=min(dp[o[i]],dp[stack[ot]]+(Dist[o[i]]-Dist[stack[ot]])*p[o[i]]+q[o[i]]);         }    }         for (int i=head[now]; i; i=edge[i].next)         if (edge[i].to!=fa[now] && !visit[edge[i].to]) {            visit[edge[i].to]=1;            Sz=size[edge[i].to];            Divide(edge[i].to);        }     }   int main(){    N=read(),T=read();    for (int i=2; i<=N; i++) {        int a=read(),b=read(); p[i]=read(),q[i]=read(),l[i]=read();        InsertEdge(i,a,b);    }    DFS(1,0);         for (int i=2; i<=N; i++) dp[i]=(1LL<<60);    Sz=mx[root=0]=N;    Divide(1);         for (int i=2; i<=N; i++) printf("%lld\n",dp[i]);         return 0;}