观察一下部分分，我们发现链上的部分分是这样一个DP：
$dp[i]=min(dp[i],dp[j]+dis(i,j)*p[i]+q[i])(dis(i,j)<=lim[i]&&j∈anc(i))$
对于可以对$i$转移的两个位置$j$和$k$，假设$dep[j]>dep[k]$且$j$比$k$优，那么倒腾一下式子
$dp[j]+dis(i,j)*p[i]+q[i]<dp[k]+dis(i,k)*p[i]+q[i]$
$dp[j]-dp[k]<(dis(i,k)-dis(i,j))*p[i]$
$frac{dp[j]-dp[k]}{dis(i,k)-dis(i,j)}<p[i]$
因为$dis$是单调的，这个东西可以使用斜率优化，因为$p[i]$不单调每次需要二分来转移
然后问题来了，现在不是棵树，如果提出来每条链来做是O(叶子数*len)的，会被扫帚图卡掉，于是有了各种优化来做这道题：
Sol1：用轻重链剖分优化，直接以一个log的代价把整条链拼出来，再用一个log的数据结构维护，复杂度$O(nlog^3 n)$
Sol2：用可持久化数据结构维护单调队列或者用待撤销的二进制分组，利用上面一段已经处理好的链分别处理每个叶子，只需要一个log，复杂度$O(nlog^2 n)$
Sol3(我写的这个)：不用数据结构维护，用点分治的方法，每次把重心和它子树外的部分递归处理，然后DFS重心的子树，子树里的节点按向上延伸后的深度排序后DP，之后再处理每一棵子树。排序和DP的log是并列的，复杂度$O(nlog^2 n)$
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=200005,inf=1e9; 6 int n,t,c,cnt,top,tpp,tsiz,maxx; 7 int fth[N],p[N],noww[N],goal[N],siz[N],vis[N],stk[N],sta[N]; 8 long long len[N],val[N],dis[N],pr1[N],pr2[N],lim[N],dp[N],rd; 9 bool cmp(int a,int b) 10 { 11 return dis[a]-lim[a]>dis[b]-lim[b]; 12 } 13 double Slope(int a,int b) 14 { 15 return (double)(dp[b]-dp[a])/(double)(dis[b]-dis[a]); 16 } 17 void Link(int f,int t,long long v) 18 { 19 noww[++cnt]=p[f],p[f]=cnt; 20 goal[cnt]=t,val[cnt]=v; 21 } 22 void Getdis(int nde) 23 { 24 for(int i=p[nde];i;i=noww[i]) 25 dis[goal[i]]=dis[nde]+val[i],Getdis(goal[i]); 26 } 27 void Mark(int nde,int sze) 28 { 29 siz[nde]=1; int tmp=0; 30 for(int i=p[nde];i;i=noww[i]) 31 if(!vis[goal[i]]) 32 { 33 Mark(goal[i],sze); 34 siz[nde]+=siz[goal[i]]; 35 tmp=max(tmp,siz[goal[i]]); 36 } 37 tmp=max(tmp,sze-siz[nde]); 38 if(tmp<=maxx) maxx=tmp,c=nde; 39 } 40 void DFS(int nde) 41 { 42 stk[++top]=nde; 43 for(int i=p[nde];i;i=noww[i]) 44 if(!vis[goal[i]]) DFS(goal[i]); 45 } 46 void DP(int nde,int anc) 47 { 48 for(int i=1;i<=top;i++) 49 { 50 int nod=stk[i]; 51 while(nde!=fth[anc]&&dis[nod]-dis[nde]<=lim[nod]) 52 { 53 while(tpp>=2&&Slope(sta[tpp],nde)>=Slope(sta[tpp-1],sta[tpp])) 54 tpp--; sta[++tpp]=nde,nde=fth[nde]; 55 } 56 if(tpp) 57 { 58 int l=1,r=tpp,best; 59 while(l<=r) 60 { 61 int mid=(l+r)/2; 62 double s=(mid==tpp)?-inf:Slope(sta[mid],sta[mid+1]); 63 if(s<=pr1[nod]) r=mid-1,best=mid; else l=mid+1; 64 } 65 best=sta[best],dp[nod]=min(dp[nod],dp[best]+(dis[nod]-dis[best])*pr1[nod]+pr2[nod]); 66 } 67 } 68 } 69 void PDC(int nde,int sze) 70 { 71 if(sze<=1) return; 72 maxx=inf,Mark(nde,sze); int hc=c; 73 for(int i=p[hc];i;i=noww[i]) 74 vis[goal[i]]=true,sze-=siz[goal[i]]; 75 PDC(nde,sze),top=0; 76 for(int i=p[hc];i;i=noww[i]) DFS(goal[i]); 77 sort(stk+1,stk+1+top,cmp),tpp=0,DP(hc,nde); 78 for(int i=p[hc];i;i=noww[i]) PDC(goal[i],siz[goal[i]]); 79 } 80 int main() 81 { 82 scanf("%d%d",&n,&t); 83 for(int i=2;i<=n;i++) 84 { 85 scanf("%d%lld",&fth[i],&rd),Link(fth[i],i,rd); 86 scanf("%lld%lld%lld",&pr1[i],&pr2[i],&lim[i]),dp[i]=1e18; 87 } 88 Getdis(1),PDC(1,n); 89 for(int i=2;i<=n;i++) printf("%lld ",dp[i]); 90 return 0; 91 }