题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3672
题意：给出一棵有根树（1为根），边有长度。每个点u有三个属性（len[u],p[u],q[u]）,每次u可以转移到u的某个祖先节点v（v满足dist(u,v)<=len[u]）,代价为p[u]*dist(u,v)+q[u]。求每个点都转移到1的代价。
思路：首先设f[u]表示u转移到1的最小代价，那么我们可以得到一个DP方程： f[u]=min(f[v]+p[u]*(s[u]-s[v])+q[u]) (v为u的祖先节点,s[u]表示u到根节点1的距离，s[u]-s[v]<=len[u])。
将上面的式子变形：f[u]=(-s[v]*p[u]+f[v])+(s[u]*p[u]+q[u])。其中s[u]*p[u]+q[u]对于u为定值那么我们只要求-s[v]*p[u]+f[v]的最小值即可。
我们按照深度由小大到的顺序依次计算，那么计算u时，它的所有祖先节点都已经计算过，他们的f[v]和s[v]值都已经知道。那么，我们断然是不能一个一个枚举u的所有祖先的.因此如何维护呢？设k=-s[v],b=f[v]，x=p[u]，y=kx+b，我们现在就是求y的最小值，k<0，斜率k，y轴截距b。我们发现，只要维护[1,fa[u]]这些点组成的上凸壳即可。
我们设现在已经维护了一个上凸壳，现在加入一个点(-s[t],f[t])，我们发现，由于题目说边的距离严格大于0，那么这个s[t]是严格递增的，也就是斜率越来越趋近于负无穷，因此，我们首先将其加入到已经维护的凸壳的最后即可（当x很大时一定是这个新加入的能够使得答案最小）。此时，前面可能有一些不再是最优值，我们只要依次从后向前判断，不是最优值就删掉，因此用一个vector维护即可（不用splay、set什么的了）。
因此，我们得到算法：
（1）首先，树链剖分，用线段树维护每个链，线段树每个节点用一个vector维护这个区间的点组成的上凸壳
（2）按照深度由小到大依次计算。由于这里有一个距离限制，那么对于u，最后我们需要查询的是一段区间[v,fa[u]]，v是满足s[u]-s[v]<=len[u]的深度最小的u的祖先。
（3）计算完节点u后将其插入到线段树中包含该点的所有区间。
const i64 inf=(1LL<<62);const int mod=1000000007;const int N=200005; vector g[N];int n,t;int fa[N];i64 len[N],p[N],q[N],dis[N]; int sonNum[N];int dep[N]; i64 s[N]; void DFS(int u){ sonNum[u]=1; int i; for(i=0;i > root;}; node A[N<<2]; void build(int t,int L,int R){ A[t].L=L; A[t].R=R; A[t].root.clear(); if(L==R) { return; } int M=(L+R)>>1; build(t<<1,L,M); build(t<<1|1,M+1,R);} #define pdd pair i64 f[N]; double cross(pdd a,pdd b){ return 1.0*(a.second-b.second)/(b.first-a.first);} int sgn(double x){ if(x>1e-20) return 1; if(x<-1e-20) return -1; return 0;}void add(vector > &x,i64 s,i64 f){ pdd p3=MP(s,f); while(SZ(x)>=2) { pdd p2=x[SZ(x)-1]; pdd p1=x[SZ(x)-2]; double x1=cross(p2,p3); double x2=cross(p1,p3); if(sgn(x1-x2)==1) break; x.pop_back(); } if(SZ(x)==1&&f<=x[0].second) x.pop_back(); x.pb(p3);} void add(int t,int pos,i64 s,i64 f){ add(A[t].root,s,f); if(A[t].L==A[t].R) return; int M=(A[t].L+A[t].R)>>1; if(pos<=M) add(t<<1,pos,s,f); else add(t<<1|1,pos,s,f);} i64 curX; i64 get(vector x){ int L=0,R=SZ(x)-1; while(R-L>=4) { int M=(R+L)>>1; double xx=cross(x[M-1],x[M]); if(sgn(xx-curX)>=0) R=M; else L=M; } i64 ans=inf; int i; for(i=L;i<=R;i++) { pdd p=x[i]; i64 tmp=curX*p.first+p.second; if(tmp >1; i64 ans=cal(t<<1|1,M+1,R,len); u1=mp[A[t<<1].R]; len-=(s[u2]-s[u1]); if(len<0) return ans; i64 tmp=cal(t<<1,L,M,len); if(tmp >1; if(R<=M) return cal(t<<1,L,R,len); if(L>M) return cal(t<<1|1,L,R,len); i64 ans=cal(t<<1|1,M+1,R,len); int u1=mp[A[t<<1].R]; int u2=mp[R]; len-=(s[u2]-s[u1]); if(len<0) return ans; i64 tmp=cal(t<<1,L,M,len); if(tmp =0) { i64 tmp=cal(1,pos[belong[u]],pos[u],L); if(tmp