题目大意：
略 题面传送门
怎么看也是一道$duliu$题= =
先推式子，设$dp[x]$表示到达$x$点到达1节点的最小花费
设$y$是$x$的一个祖先，则$dp[x]=min(dp[y]+(dis[x]-dis[y])*p[x]+q[x])$，且$dis[x]-dis[y] leq lim[x]$
猜也能猜出来是斜率优化
展开，$dp[y]=p[x]*dis[y];+dp[x]-dis[x]*p[x]+q[x]$
此外，$dis$在上述式子中作为一次函数$y=kx+b$的$x$项，且$dis$保证在$1$节点到某点的链上递增，这个性质会很有用
接下来的问题就是如何构造凸包了
方案一：无脑的树剖
把树上的点按照$dis$从小到大排序，依次处理
用树剖+线段树维护可持久化凸包，每次询问都取出能用于转移的那些凸包。
斜率$p$并不单调，那么每次切凸包都要二分
而有了$lim[i]$的限制，我们不能保证所有的祖先节点都能用于转移，倍增跳到最远的合法祖先
树剖，线段树，二分凸包，$O(nlog^{3}n)$，这三个$log$理论上都跑不满，实测跑得确实挺快的。想卡树剖放下述两个方法过也没那么容易
考试的时候还犹豫什么当然是写树剖啦
1 #include <map> 2 #include <queue> 3 #include <vector> 4 #include <cstdio> 5 #include <cstring> 6 #include <algorithm> 7 #define N1 201000 8 #define ll long long 9 #define dd double 10 #define inf 23333333333333333ll 11 #define it map<node,int>::iterator 12 using namespace std; 13 14 int gint() 15 { 16 int ret=0,fh=1;char c=getchar(); 17 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 18 while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();} 19 return ret*fh; 20 } 21 int n,T; 22 struct Edge{ 23 int to[N1<<1],nxt[N1<<1],head[N1],cte;ll val[N1<<1]; 24 void ae(int u,int v,ll w) 25 { 26 cte++;to[cte]=v,val[cte]=w; 27 nxt[cte]=head[u],head[u]=cte; 28 } 29 }e; 30 struct SEG{ 31 int cvh[21][N1]; 32 int TP[N1<<2]; ll *X,*Y; 33 void build(int l,int r,int rt,int dep) 34 { 35 TP[rt]=l-1; 36 if(l==r) return; 37 int mid=(l+r)>>1; 38 build(l,mid,rt<<1,dep+1); 39 build(mid+1,r,rt<<1|1,dep+1); 40 } 41 void push(int *c,int l,int &tp,int id) 42 { 43 while(tp>l&&(1.0*Y[id]-1.0*Y[c[tp-1]])/(1.0*X[id]-1.0*X[c[tp-1]])<=(1.0*Y[c[tp]]-1.0*Y[c[tp-1]])/(1.0*X[c[tp]]-1.0*X[c[tp-1]])) 44 tp--; 45 c[++tp]=id; 46 } 47 ll cut(int *c,int l,int &tp,ll K) 48 { 49 if(tp<l) return inf; 50 if(l==tp) return Y[c[tp]]-K*X[c[tp]]; 51 int r=tp,ans=l,mid; l++; 52 while(l<=r) 53 { 54 mid=(l+r)>>1; 55 if((1.0*Y[c[mid]]-1.0*Y[c[mid-1]])/(1.0*X[c[mid]]-1.0*X[c[mid-1]])<=1.0*K) ans=mid,l=mid+1; 56 else r=mid-1; 57 } 58 return Y[c[ans]]-K*X[c[ans]]; 59 } 60 void update(int x,int l,int r,int rt,int id,int dep) 61 { 62 push(cvh[dep],l,TP[rt],id); 63 if(l==r) return; int mid=(l+r)>>1; 64 if(x<=mid) update(x,l,mid,rt<<1,id,dep+1); 65 else update(x,mid+1,r,rt<<1|1,id,dep+1); 66 } 67 ll query(int L,int R,int l,int r,int rt,ll K,int dep) 68 { 69 if(L<=l&&r<=R) return cut(cvh[dep],l,TP[rt],K); 70 int mid=(l+r)>>1; ll ans=inf; 71 if(L<=mid) ans=min(ans,query(L,R,l,mid,rt<<1,K,dep+1)); 72 if(R>mid) ans=min(ans,query(L,R,mid+1,r,rt<<1|1,K,dep+1)); 73 return ans; 74 } 75 }s; 76 77 ll P[N1],Q[N1],L[N1],f[N1],dis[N1]; 78 int lg[N1]; 79 namespace tr{ 80 int st[N1],ed[N1],id[N1],tot,ff[N1][21]; 81 int dep[N1],fa[N1],tp[N1],son[N1],sz[N1]; 82 void dfs1(int u,int dad) 83 { 84 sz[u]=1; ff[u][0]=u; 85 for(int j=e.head[u];j;j=e.nxt[j]) 86 { 87 int v=e.to[j]; if(v==dad) continue; 88 dis[v]=dis[u]+e.val[j]; dep[v]=dep[u]+1; 89 fa[v]=u; ff[v][1]=u; dfs1(v,u); 90 sz[u]+=sz[v]; if(sz[v]>sz[son[u]]) son[u]=v; 91 } 92 } 93 void dfs2(int u) 94 { 95 st[u]=++tot; id[tot]=u; 96 if(son[u]) tp[son[u]]=tp[u],dfs2(son[u]); 97 for(int j=e.head[u];j;j=e.nxt[j]) 98 { 99 int v=e.to[j]; 100 if(v==fa[u]||v==son[u]) continue; 101 tp[v]=v; dfs2(v); 102 } 103 ed[u]=tot; 104 } 105 void init() 106 { 107 int i,j; s.build(1,n,1,0); 108 s.X=dis,s.Y=f; s.update(1,1,n,1,1,0); 109 dfs1(1,-1); tp[1]=1; dfs2(1); 110 for(j=2;j<=lg[n]+1;j++) 111 for(i=1;i<=n;i++) 112 ff[i][j]=ff[ ff[i][j-1] ][j-1]; 113 } 114 void solve(int x) 115 { 116 int y=x,j,z; f[x]=inf; 117 while(dis[x]-dis[tp[y]]<=L[x]&&y) 118 f[x]=min(f[x],s.query(st[tp[y]],st[y],1,n,1,P[x],0)),y=fa[tp[y]]; 119 if(y&&dis[x]-dis[y]<=L[x]) 120 { 121 for(z=y,j=lg[dep[y]]+1;j>=0;j--) 122 if(dis[x]-dis[ff[z][j]]<=L[x]) z=ff[z][j]; 123 f[x]=min(f[x],s.query(st[z],st[y],1,n,1,P[x],0)); 124 } 125 f[x]+=dis[x]*P[x]+Q[x]; 126 s.update(st[x],1,n,1,x,0); 127 } 128 }; 129 130 int id[N1]; 131 int cmp(int x,int y){return dis[x]<dis[y];} 132 133 int main() 134 { 135 //freopen("t2.in","r",stdin); 136 freopen("testdata.in","r",stdin); 137 int i,x; ll w; 138 scanf("%d%d",&n,&T); 139 for(lg[1]=0,i=2;i<=n;i++) lg[i]=lg[i>>1]+1; 140 for(id[1]=1,i=2;i<=n;i++) 141 { 142 scanf("%d%lld%lld%lld%lld",&x,&w,&P[i],&Q[i],&L[i]); 143 e.ae(x,i,w); id[i]=i; //e.ae(i,x,w); 144 } 145 tr::init(); 146 sort(id+1,id+n+1,cmp); 147 for(i=2;i<=n;i++) 148 tr::solve(id[i]); 149 for(i=2;i<=n;i++) 150 printf("%lld ",f[i]); 151 return 0; 152 }
方案二：有点玄学的点分治
假如把我们这个问题放到序列上会发生什么？
嗯，变成了一道$CDQ$分治题
那$CDQ$上树会发生什么？
它变成了点分治
请忽略上述沙雕分析
$CDQ$的思想是递归左区间，然后处理左区间对右区间的影响，再递归右区间
很好，那么序列上分“左右”的方法是取$mid$，树上的方法变成了找重心
假设我们现在找到了一个重心$x$，它到$1$节点的路径上所有点，都可能对$x$的所有子树(除了包含$1$节点的子树)产生影响
而$1$到$x$的链上还有一些点没有取到最优解
所以需要在包含$1$节点的子树继续递归
而$x$节点的信息也需要用于转移，所以我们要把$x$的其他子树砍掉，然后把$x$节点加入到包含$1$节点的那个子树里去递归
递归求得$1$到$x$链上每个节点的最优解后，处理这个链上每个点对其他子树内节点的影响
其他节点能取到的最小深度是$dis[x]-lim[x]$
我们要避免从凸包内删除节点的尴尬情况
利用一个性质，$dis$在$1$到$x$的链上一定是递增的
所以，把其他节点按照$dis[x]-lim[x]$从大到小排序
每遍历到一个节点$x$，就把链上深度较大的节点$y$依次加入凸包，直到不满足$dis[x]-lim[x]<=dis[y]$
由于点是按$x$轴从右往左加进去的，我们实际想要维护的是一个下凸包，所以要写成维护上凸包的形式
接下来要继续递归其他子树了
我们已经处理过了$1$到$x$这条链对其他子树的影响了
所以只需要处理 某子树最靠近$1$节点的节点 到 某颗子树重心 这条链对该子树的影响即可
然后把上述操作中的 $1$节点 换成 该子树最靠近$1$节点的节点 就行了
我写得很恶心，应该是我代码能力太弱的原因qwq
1 #include <queue> 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #define N1 201000 7 #define ll long long 8 #define dd double 9 #define inf 0x3f3f3f3f3f3f3f3fll 10 using namespace std; 11 12 int gint() 13 { 14 int ret=0,fh=1;char c=getchar(); 15 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 16 while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();} 17 return ret*fh; 18 } 19 int n,T; 20 struct Edge{ 21 int to[N1<<1],nxt[N1<<1],head[N1],cte;ll val[N1<<1]; 22 void ae(int u,int v,ll w) 23 { 24 cte++;to[cte]=v,val[cte]=w; 25 nxt[cte]=head[u],head[u]=cte; 26 } 27 }e; 28 ll P[N1],Q[N1],lim[N1],f[N1],dis[N1]; ll *X,*Y; 29 int tsz,G,sz[N1],use[N1],fa[N1],ms[N1]; 30 int q[N1],qe,s[N1],se,stk[N1],tp,instk[N1]; 31 void gsz(int u,int dad) 32 { 33 sz[u]=1; 34 for(int j=e.head[u];j;j=e.nxt[j]) 35 { 36 int v=e.to[j]; if(v==dad||use[v]||instk[v]) continue; 37 gsz(v,u); 38 sz[u]+=sz[v]; 39 } 40 } 41 void gra(int u,int dad) 42 { 43 ms[u]=0; 44 for(int j=e.head[u];j;j=e.nxt[j]) 45 { 46 int v=e.to[j]; if(v==dad||use[v]||instk[v]) continue; 47 gra(v,u); 48 ms[u]=max(ms[u],sz[v]); 49 } 50 ms[u]=max(ms[u],tsz-sz[u]); 51 if(ms[u]<ms[G]) G=u; 52 } 53 int cmp(int x,int y){return dis[x]-lim[x]>dis[y]-lim[y];} 54 int que[N1],fr[N1],hd,tl; 55 void bfs(int u,int dad) 56 { 57 int x; hd=tl=1; que[1]=u; fr[u]=dad; 58 while(hd<=tl) 59 { 60 x=que[hd++]; q[++qe]=x; 61 for(int j=e.head[x];j;j=e.nxt[j]) 62 if(!use[e.to[j]]&&e.to[j]!=fr[x]) 63 que[++tl]=e.to[j],fr[e.to[j]]=x; 64 } 65 } 66 void calc(int u,int rt) 67 { 68 int x=u,y,i,j,v,l,r,ans,mid; 69 while(x!=rt) s[++se]=x,x=fa[x]; s[++se]=rt; 70 for(j=e.head[u];j;j=e.nxt[j]) 71 { 72 v=e.to[j]; if(use[v]||v==fa[u]) continue; 73 bfs(v,u); 74 } 75 sort(q+1,q+qe+1,cmp); 76 for(i=1,j=1;j<=qe;j++) 77 { 78 x=q[j]; 79 for(;i<=se&&dis[x]-lim[x]<=dis[s[i]];i++) 80 { 81 y=s[i]; 82 if(dis[x]-lim[x]<=dis[y]) 83 { 84 while(tp>1&&(1.0*Y[y]-1.0*Y[stk[tp-1]])/(1.0*X[y]-1.0*X[stk[tp-1]])>=(1.0*Y[stk[tp]]-1.0*Y[stk[tp-1]])/(1.0*X[stk[tp]]-1.0*X[stk[tp-1]])) 85 tp--; 86 stk[++tp]=y; 87 } 88 } 89 if(!tp) continue; 90 l=1,r=tp-1,ans=tp; 91 while(l<=r) 92 { 93 mid=(l+r)>>1; 94 if((1.0*Y[stk[mid]]-1.0*Y[stk[mid+1]])/(1.0*X[stk[mid]]-1.0*X[stk[mid+1]])<=1.0*P[x]) ans=mid,r=mid-1; 95 else l=mid+1; 96 } 97 f[x]=min(f[x],f[stk[ans]]+(dis[x]-dis[stk[ans]])*P[x]+Q[x]); 98 } 99 tp=0,qe=0,se=0; 100 } 101 vector<int>tmp[N1]; 102 void main_dfs(int u,int rt) 103 { 104 int j,v; use[u]=1; gsz(u,-1); instk[u]=1; 105 if(!use[fa[u]]&&u!=rt) 106 { 107 for(j=e.head[u];j;j=e.nxt[j]) 108 { 109 v=e.to[j]; if(use[v]||v==fa[u]) continue; 110 tmp[u].push_back(v); use[v]=1; 111 } 112 v=fa[u]; tsz=sz[v]; G=0; gra(v,-1); use[u]=0; 113 main_dfs(G,rt); 114 for(j=0;j<tmp[u].size();j++) 115 { 116 v=tmp[u][j]; 117 use[v]=0; 118 } 119 tmp[u].clear(); 120 use[u]=1; 121 } 122 calc(u,rt); 123 for(j=e.head[u];j;j=e.nxt[j]) 124 { 125 v=e.to[j]; if(use[v]||instk[v]||v==fa[u]) continue; 126 G=0; tsz=sz[v]; gra(v,-1); 127 main_dfs(G,v); 128 } 129 instk[u]=0; 130 } 131 void pre_dfs(int u) 132 { 133 for(int j=e.head[u];j;j=e.nxt[j]) 134 { 135 int v=e.to[j]; if(v==fa[u]) continue; 136 dis[v]=dis[u]+e.val[j]; pre_dfs(v); 137 } 138 } 139 140 int main() 141 { 142 int i,x; ll w; 143 scanf("%d%d",&n,&T); 144 for(i=2;i<=n;i++) 145 { 146 scanf("%d%lld%lld%lld%lld",&fa[i],&w,&P[i],&Q[i],&lim[i]); 147 e.ae(fa[i],i,w); e.ae(i,fa[i],w); 148 } 149 X=dis,Y=f; pre_dfs(1); 150 memset(f,0x3f,sizeof(f)); f[1]=0; 151 tsz=ms[0]=n; G=0; gsz(1,-1); gra(1,-1); 152 main_dfs(G,1); 153 for(i=2;i<=n;i++) 154 printf("%lld ",f[i]); 155 return 0; 156 }
方案三：二进制分组？？
一会再看
凸包不建议用$vector$维护，开$logn$层数组，线段树内每个位置都记录凸包的开头结尾指针
另外叉积会爆$longlong$，$double$精度足够