Description：

给一棵树，每个点都想走到根，每个点 $k$ 可以走到他的一个祖先 $anc$ 要求 $dis(k,anc)\leqslant l_k$ ，花费 $s_k\times dis(k,anc)+b_k$ 的花费，求每个节点到根的花费。

$1\leqslant n\leqslant 2\times10^5$

Solution1：

首先上面那个式子显然是可以斜率优化的，即 $f[k]=\min(f[anc]+s_k\times dep[k]-s_k\times dep[anc]+b_k)(dep[k]-dep[anc]\leqslant l_k)$ ，那么如果没有那个距离限制我们就可以在 $dfs$ 的栈上维护一个凸包，然后每次在凸包上二分最优解，因为 $-s_k$ 不单调，但是由于距离的限制，在之前一定不会成为最优解的在之后可能成为决策点，所以我们就必须换一种做法。

先考虑在序列上怎么做，可以使用 $cdq$ 分治，我们知道 $cdq$ 分治的一个重要作用就是去掉左右区间内部的时间顺序，那么我们就可以按右区间每个点能延伸到的左端点从右向左排序，也就是说在左区间中的覆盖范围逐渐增大，然后逐步构造出左区间形成的凸包，每次让右区间在对应部分二分最优解并随着覆盖范围逐渐在凸包中插入点即可，由于 $dep[anc]$ 是单调的所以用单调栈维护凸包就行了。

考虑怎么把它扩展到树上，发现分治实际就是找中点然后分为两部分，那么对于树我们可以利用点分治，把整棵树分为从根到重心和重心的子树，然后像在序列上一样用从根到重心的值更新重心的子树的值就行了。

Code1：

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

int n;

#define MAXN 200010

typedef long long ll;

struct edge

{

    int to,nxt;

    ll v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll c)

{

    e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

    e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

    return;

}

ll p[MAXN],q[MAXN],g[MAXN];

int fa[MAXN],anc[MAXN];

ll dep[MAXN];

int stack[MAXN],top = 0;

void dfs(int k,ll depth)

{

    dep[k] = depth;

    stack[++top] = k;

    int l = 1,r = top,mid;

    while(l < r)

    {

        mid = ((l + r) >> 1);

        if(dep[k] - dep[stack[mid]] <= g[k])r = mid;

        else l = mid + 1;

    }

    anc[k] = stack[l];

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(dep[e[i].to] == 0)

        {

            fa[e[i].to] = k;

            dfs(e[i].to,depth + e[i].v);

        }

    }

    --top;

    return;

}

int s,root,siz[MAXN],d[MAXN];

#define INF 0x3f3f3f3f

bool vis[MAXN];

void getsiz(int k,int fa)

{

    siz[k] = 1;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to == fa || vis[e[i].to])continue;

        getsiz(e[i].to,k);

        siz[k] += siz[e[i].to];

    }

    return;

}

void getroot(int k,int fa)

{

    siz[k] = 1;d[k] = 0;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to == fa || vis[e[i].to])continue;

        getroot(e[i].to,k);

        siz[k] += siz[e[i].to];

        d[k] = max(d[k],siz[e[i].to]);

    }

    d[k] = max(d[k],s - siz[k]);

    if(d[k] < d[root])root = k;

    return;

}

struct state{int top,id;}t[MAXN];

bool cmp_top(state a,state b){return dep[a.top] > dep[b.top];}

int tot = 0;

void get(int k,int fa)

{

    t[++tot] = (state){anc[k],k};

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(vis[e[i].to] || e[i].to == fa)continue;

        get(e[i].to,k);

    }

    return;

}

int hull[MAXN],htop = 0;

ll f[MAXN];

ll x(int k){return dep[k];}

ll y(int k){return f[k];}

double slope(int a,int b){return double(y(a) - y(b)) / double(x(a) - x(b));}

void calc(int k)

{

    getsiz(k,0);

    s = siz[k];d[0] = INF;root = 0;

    getroot(k,0);

    k = root;

    int topp = k;

    while(fa[topp] != 0 && !vis[fa[topp]])topp = fa[topp];

    vis[k] = true;

    if(!vis[fa[k]] && fa[k] != 0)calc(fa[k]);

    tot = 0;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(vis[e[i].to])continue;

        get(e[i].to,k);

    }

    for(int i = fa[k];i != fa[topp];i = fa[i])

    {

        if(dep[k] - dep[i] > g[k])break;

        f[k] = min(f[k],f[i] + p[k] * dep[k] - p[k] * dep[i] + q[k]);

    }

    sort(t + 1,t + 1 + tot,cmp_top);

    htop = 0;

    for(int j = 1,i = k;j <= tot;++j)

    {

        while(i != fa[topp] && dep[t[j].top] <= dep[i])

        {

            while(htop >= 2 && slope(i,hull[htop]) >= slope(hull[htop],hull[htop - 1]))--htop;

            hull[++htop] = i;

            i = fa[i];

        }

        int pos = t[j].id;

        int l = 1,r = htop,midl,midr;

        ll resl,resr;

        ll res = 0x3f3f3f3f3f3f3f3f;

        while(l <= r)

        {

            int len = (r - l + 3) / 3;

            midl = l + len - 1;midr = r - len + 1;

            resl = f[hull[midl]] + p[pos] * dep[pos] - p[pos] * dep[hull[midl]] + q[pos];

            resr = f[hull[midr]] + p[pos] * dep[pos] - p[pos] * dep[hull[midr]] + q[pos];

            res = min(res,min(resl,resr));

            if(resl < resr)r = midr - 1;

            else l = midl + 1;

        }

        f[pos] = min(f[pos],res);

    }

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(!vis[e[i].to])calc(e[i].to);

    }

    return;

}

int main()

{

    int x;

    scanf("%d%d",&n,&x);

    int dad,len;

    for(int i = 2;i <= n;++i)

    {

        scanf("%d%d%lld%lld%lld",&dad,&len,&p[i],&q[i],&g[i]);

        add(dad,i,len);

    }

    memset(f,0x3f,sizeof(f));

    f[1] = 0;

    dfs(1,1);

    calc(1);

    for(int i = 2;i <= n;++i)printf("%lld\n",f[i]);

    return 0;

}

Solution2：

考虑那个之前在 $dfs$ 的栈上维护凸包的做法，我们可以利用二进制分组来模拟栈，即用一棵线段树来维护这个栈，然后每次在 $\log$ 个区间的凸包上查询最优解，但是这要求我们的二进制分组支持撤销，正确的做法是线段树每一层不维护最后一个满了的节点，也就是说每次把上一个区间的凸包构造出来，这样复杂度就是对的了，证明的话可以参考算法导论动态表的收缩和扩张，注意线段树必须是二的整次幂。

Code2：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

typedef long long ll;

struct edge

{

	int to,nxt;

	ll v;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	return;

}

ll p[MAXN],q[MAXN],d[MAXN];

ll dep[MAXN];

int N;

struct node

{

	int lc,rc;

	vector<int> v;

}t[MAXN << 2];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

int pre[MAXN << 2],last[MAXN];

void build(int &rt,int l,int r)

{

	rt = newnode();

	pre[rt] = last[r - l + 1];last[r - l + 1] = rt;

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

int tmp[MAXN],hull[MAXN],htop;

bool cmp_x(int a,int b){return dep[a] < dep[b];}

ll f[MAXN];

double slope(int a,int b){return double(f[a] - f[b]) / double(dep[a] - dep[b]);}

bool maintained[MAXN << 2];

void merge(int rt,int l,int r)

{

	if(rt == 0)return;

	if(l == r)return;

	maintained[rt] = true;

	t[rt].v.clear();

	int lc = t[rt].lc,rc = t[rt].rc;

	tmp[0] = 0;

	for(vector<int>::iterator it = t[lc].v.begin();it != t[lc].v.end();++it)tmp[++tmp[0]] = *it;

	for(vector<int>::iterator it = t[rc].v.begin();it != t[rc].v.end();++it)tmp[++tmp[0]] = *it;

	sort(tmp + 1,tmp + 1 + tmp[0],cmp_x);

	htop = 0;

	for(int i = 1;i <= tmp[0];++i)

	{

		while(htop >= 2 && slope(tmp[i],hull[htop]) <= slope(hull[htop],hull[htop - 1]))--htop;

		hull[++htop] = tmp[i];

	}

	for(int i = 1;i <= htop;++i)t[rt].v.push_back(hull[i]);

	return;

}

void insert(int rt,int p,int k,int l,int r)

{

	if(l == r)

	{

		maintained[rt] = true;

		t[rt].v.push_back(k);

		return;

	}

	if(p <= mid)insert(t[rt].lc,p,k,l,mid);

	else insert(t[rt].rc,p,k,mid + 1,r);

	if(p == r)merge(pre[rt],l - (r - l + 1),l - 1);

	return;

}

void remove(int rt,int p,int l,int r)

{

	t[rt].v.clear();

	maintained[rt] = false;

	if(l == r)return;

	if(p <= mid)remove(t[rt].lc,p,l,mid);

	else remove(t[rt].rc,p,mid + 1,r);

	return;

}

#define INFLL 0x3f3f3f3f3f3f3f3f

ll calc(vector<int> v,int k)

{

	int l = 0,r = v.size() - 1,midl,midr;

	ll resl,resr,res = INFLL;

	while(l <= r)

	{//cout << "$$$ " << l << " " << r << endl;

		int len = (r - l + 3) / 3;

		midl = l + len - 1;midr = r - len + 1;

		resl = f[v[midl]] + p[k] * (dep[k] - dep[v[midl]]) + q[k];

		resr = f[v[midr]] + p[k] * (dep[k] - dep[v[midr]]) + q[k];

		res = min(res,min(resl,resr));

		if(resl < resr)r = midr - 1;

		else l = midl + 1;

	}//cout << "###" << endl;

	return res;

}

ll query(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{//cout << l << " " << r << endl;

		if(maintained[rt])return calc(t[rt].v,k);

		else return min(calc(t[t[rt].lc].v,k),query(t[rt].rc,L,R,k,mid + 1,r));

	}

	long long res = INFLL;

	if(L <= mid)res = min(res,query(t[rt].lc,L,R,k,l,mid));

	if(R > mid)res = min(res,query(t[rt].rc,L,R,k,mid + 1,r));

	return res;

}

int stack[MAXN],top = 0;

void dfs(int k)

{

	stack[++top] = k;

	int l = 1,r = top,md;

	while(l < r)

	{

		md = ((l + r) >> 1);

		if(dep[k] - dep[stack[md]] <= d[k])r = md;

		else l = md + 1;

	}

	insert(root,top,k,1,N);//cout << "st" << endl;

	f[k] = query(root,l,top,k,1,N);//cout << "ed" << endl;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dep[e[i].to] = dep[k] + e[i].v;

		dfs(e[i].to);

	}

	remove(root,top,1,N);

	--top;

	return;

}

int main()

{

	int x;

	scanf("%d%d",&n,&x);

	N = 1;

	while(N < n)N = N << 1;

	build(root,1,N);

	int fa;ll len;

	for(int i = 2;i <= n;++i)

	{

		scanf("%d%lld%lld%lld%lld",&fa,&len,&p[i],&q[i],&d[i]);

		add(fa,i,len);

	}

	memset(f,0x3f,sizeof(f));f[1] = 0;

	dfs(1);

	for(int i = 2;i <= n;++i)printf("%lld\n",f[i]);

	return 0;

}

Solution3：

考虑利用树剖转移，也就是说先把树进行树链剖分，线段树维护凸壳，因为询问的区间是他到根的一条链，所以只有在这个区间都插入之后合并子节点的凸包，这样就只有插入了，然后 $dfs$ 做就没了，时间复杂度 $O(n\log^3 n)$ 。

Code3：