斜率优化+点分治(CDQ?)

首先处理一个分治中心到这一块子树的最高点(子树的根)的链上的DP值

优先分治处理包含根的子树，然后再处理其他子树

#include
     
      #include
      
       using namespace std;long long root,Num,N,st,Top,cnt,last[1000005],sz[1000005],F_[1000005],p[1000005],q[1000005],lim[1000005],Dep[1000005],Fa[1000005],vis[1000005];long long F[1000005];struct node1{	long long k,b;}stack[1000005];struct node2{	long long x,val;}E[1000005];struct node{	int to,next;	long long val;}e[1000005];void add(int a,int b,long long c){	e[++cnt].to=b;	e[cnt].next=last[a];	e[cnt].val=c;	last[a]=cnt;}void dfs(int x,int fa,long long dep){	sz[x]=1;	Dep[x]=dep;	for (int i=last[x]; i; i=e[i].next){		int V=e[i].to;		if (V==fa) continue;		dfs(V,x,dep+e[i].val);		sz[x]+=sz[V];	}}void find_root(int x,int fa){	sz[x]=1,F_[x]=0;	for (int i=last[x]; i; i=e[i].next){		int V=e[i].to;		if (vis[V] || V==fa) continue;		find_root(V,x);		sz[x]+=sz[V];		F_[x]=max(F_[x],sz[V]);	}	F_[x]=max(F_[x],N-sz[x]);	if (F_[x]
       
        b.val;}double check(node1 a,node1 b){	return ((double)a.b-b.b)/(b.k-a.k);}void insert(int x){	node1 line=(node1){-Dep[x],F[x]};	while (Top>1 && check(line,stack[Top])>=check(stack[Top],stack[Top-1])) Top--;	stack[++Top]=line;}void Divide(int x,int S){	if (S<=1) return;	root=0,N=S;	find_root(x,0);	int Root=root;	for (int i=last[Fa[root]]; i; i=e[i].next){		int V=e[i].to;		if (vis[V]) continue;		if (V==Root) {			vis[Root]=1;			Divide(x,sz[x]-sz[Root]);			break;		}	}	for (int now=Fa[Root]; now!=Fa[x]; now=Fa[now])		if (Dep[now]>=Dep[Root]-lim[Root]) F[Root]=min(F[Root],F[now]+1ll*(Dep[Root]-Dep[now])*p[Root]+q[Root]);	Num=0;	for (int i=last[Root]; i; i=e[i].next){		int V=e[i].to;		if (vis[V] || V==Fa[Root]) continue;		Pre(V,Root);	}	sort(E+1,E+Num+1,cmp);	Top=0,st=Root;	for (int i=1; i<=Num; i++){		int X=E[i].x;		while (st!=Fa[x] && Dep[st]>=Dep[X]-lim[X]){			insert(st);			st=Fa[st];		}		if (Top){			int L=1,R=Top;			while (L
        
         >1;				double l,r;				if (mid==Top) l=-1ll<<60;				else l=check(stack[mid],stack[mid+1]);				if (mid==1)  r=1ll<<60;				else r=check(stack[mid],stack[mid-1]);				if (p[X]>=l && p[X]<=r){					L=mid;					break;				}				else if (p[X]