「LOJ 2249」「NOI2014」购票

发表于

今年夏天，NOI 在 SZ 市迎来了她 30 周岁的生日。来自全国 nn 个城市的 OIer 们都会从各地出发，到 SZ 市参加这次盛会。

全国的城市构成了一棵以 SZ 市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 nn 个城市用 11 到 nn 的整数编号。其中 SZ 市的编号为 11 。对于除 SZ 市之外的任意一个城市 vv ，我们给出了它在这棵树上的父亲城市 fvf_v 以及到父亲城市道路的长度 svs_v 。

从城市 vv 前往 SZ 市的方法为：选择城市 vv 的一个祖先 aa，支付购票的费用，乘坐交通工具到达 aa。再选择城市 aa 的一个祖先 bb ，支付费用并到达 bb 。以此类推，直至到达 SZ 市。

对于任意一个城市 vv ，我们会给出一个交通工具的距离限制 lvl_v 。对于城市 vv 的祖先 aa ，只有当它们之间所有道路的总长度不超过 lvl_v 时，从城市 vv 才可以通过一次购票到达城市 aa ，否则不能通过一次购票到达。对于每个城市 vv ，我们还会给出两个非负整数 pv,qvp_v,q_v 作为票价参数。若城市 vv 到城市 aa 所有道路的总长度为 dd ，那么从城市 vv 到城市 aa 购买的票价为 dpv+qvdp_v+q_v​​ 。

每个城市的 OIer 都希望自己到达 SZ 市时，用于购票的总资金最少。你的任务就是，告诉每个城市的 OIer 他们所花的最少资金是多少。

Constraints

n≤2×105n \leq 2\times 10^5

Solution

由题意可得，令 di,jd_{i,j} 表示点 ii 到点 jj 的距离，我们利用祖先去更新节点，可以得到以下式子：

dpi=max{dpj+pi⋅di,j+qi}dp_i=max \{ dp_j+p_i\cdot d_{i,j}+q_i \}

考虑斜率优化，令点 kk 为点 jj 的祖先，则可以得到式子：dpj−dpk≥pi⋅(di,k−di,j)dp_j-dp_k \geq p_i\cdot (d_{i,k}-d_{i,j}) 。

令 disidis_i 表示点 ii 到根节点的距离，则式子可以变换为：dpj−dpkdisj−disk≥pi\frac{dp_j-dp_k}{dis_j-dis_k}\geq p_i 。

所以只需要维护凸包，每一次在凸包上二分斜率即可。为了保证复杂度，在点分治的基础上，我们将所有需要更新的点按照有效的祖先节点进行排序。处理时先处理祖先部分的节点，再用祖先部分的信息来更新其他节点。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
const LL inf=(1ll<<62);
int n,cnt,tot,now;
int first[N],fa[N],sz[N],mx[N],st[N];
LL x,p[N],q[N],L[N],dis[N],dp[N];
bool vis[N];
struct edge{int to,next;LL w;}e[N];
struct node{int id;LL v;}a[N];
LL read()
{
	LL x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void ins(int u,int v,LL w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;}
bool cmp(node a,node b){return a.v>b.v;}
LL K(int x,int y){return 1.0*(dp[y]-dp[x])/(dis[y]-dis[x]);}
LL calc(int x,int y){return dp[y]+(dis[x]-dis[y])*p[x]+q[x];}
void dfs(int x)
{
	sz[x]=1;
	for(int i=first[x];i;i=e[i].next)
	{
		dis[e[i].to]=dis[x]+e[i].w;
		dfs(e[i].to);sz[x]+=sz[e[i].to];
	}
}
void findrt(int x,int S,int& rt)
{
	mx[x]=0;sz[x]=1;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(vis[to])continue;
		findrt(to,S,rt);
		sz[x]+=sz[to];
		mx[x]=max(mx[x],sz[to]);
	}
	mx[x]=max(mx[x],S-sz[x]);
	if(mx[x]<mx[rt]&&sz[x]>1)rt=x;
}
void mark(int x)
{
	a[++tot].id=x;a[tot].v=dis[x]-L[x];
	for(int i=first[x];i;i=e[i].next)
		if(!vis[e[i].to])mark(e[i].to);
}
void solve(int x,int S)
{
	if(S==1)return;
	int rt=0;findrt(x,S,rt);
	for(int i=first[rt];i;i=e[i].next)vis[e[i].to]=true;
	solve(x,S-sz[rt]+1);
	tot=0;now=rt;
	for(int i=first[rt];i;i=e[i].next)mark(e[i].to);
	sort(a+1,a+tot+1,cmp);
	int l,r,mid,pos,tail=0;
	for(int i=1;i<=tot;i++)
	{
		while(now!=fa[x]&&a[i].v<=dis[now])
		{
			while(tail>1&&K(st[tail],now)>=K(st[tail-1],st[tail]))tail--;
			st[++tail]=now;now=fa[now];
		}
		if(tail>0)
		{
			l=1;r=tail;pos=1;
			while(l<=r)
			{
				mid=(l+r)>>1;
				if(mid==tail){pos=tail;break;}
				if(K(st[mid],st[mid+1])>=p[a[i].id])l=mid+1,pos=mid+1;
				else r=mid-1;
			}
			dp[a[i].id]=min(dp[a[i].id],calc(a[i].id,st[pos]));
		}
	}
	for(int i=first[rt];i;i=e[i].next)solve(e[i].to,sz[e[i].to]);
}
int main()
{
	n=read();read();
	for(int i=2;i<=n;i++)
	{
		fa[i]=read();x=read();ins(fa[i],i,x);
		p[i]=read();q[i]=read();L[i]=read();
	}
	dfs(1);mx[0]=n+1;
	for(int i=2;i<=n;i++)dp[i]=inf;
	solve(1,sz[1]);
	for(int i=2;i<=n;i++)printf("%lld\n",dp[i]);
	return 0;
}