noi2014购票

发表于

:shit:

题目描述

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

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

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

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

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

输入格式

第一行包含两个非负整数 $n,t$，分别表示城市的个数和数据类型（其意义将在后面提到）。
输入文件的第二到 $n$ 行，每行描述一个除 SZ 之外的城市。其中第 $v$ 行包含五个非负整数 $f_v,s_v,p_v,q_v,l_v$，分别表示城市 $v$ 的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。

请注意：输入不包含编号为 $1$ 的 SZ 市，第二行到第 $n$ 行分别描述的是城市 $2$ 到城市 $n$。

输出格式

输出包含 $n-1$ 行，每行包含一个整数。其中第 $v$ 行表示从城市 $v+1$ 出发，到达 SZ 市最少的购票费用。

同样请注意：输出不包含编号为 $1$ 的 SZ 市。

样例输入

1
2
3
4
5
6
7
7 3
1 2 20 0 3
1 5 10 100 5
2 4 10 10 10
2 9 1 100 10
3 5 20 100 10
4 4 20 0 10

样例输出

1
2
3
4
5
6
40
150
70
149
300
150

数据范围

对于所有数据，$n\leq 2 \times 10^5, 0 \leq p_v \leq 10^6,\ 0 \leq q_v \leq 10^{12},\ 1\leq f_v<v,\ 0<s_v\leq lv \leq 2 \times 10^{11}$，且任意城市到 SZ 市的总路程长度不超过 $2 \times 10^{11}$。
输入的 $t$ 表示数据类型，$0\leq t<4$，其中：
当 $t=0$ 或 $2$ 时，对输入的所有城市 $v$，都有 $f_v=v-1$，即所有城市构成一个以 SZ 市为终点的链；
当 $t=0$ 或 $1$ 时，对输入的所有城市 $v$，都有 $l_v=2 \times 10^{11}$，即没有移动的距离限制，每个城市都能到达它的所有祖先；
当 $t=3$ 时，数据没有特殊性质。

算法讨论

如果是序列上的问题，很容易得到一个斜率DP方程

其中$dis_i$为$i$到根的距离，维护一个下凸壳，在上面二分。对于题目中的距离限制，可以CDQ+排序处理

那么如果这棵树是一条链，就可以由深度从小到大依次讨论节点。

如果不是一颗链，考虑将每个叶子到根的链提出来进行DP

容易发现这样进行DP，深度较小的可以更新多个深度大的

那么考虑使用点分治，对于当前讨论的这棵树，找到它的重心。在重心将这颗树分成两半，上半部分递归处理，然后收集重心子树中的点集$V$，用重心到根的这条链建立凸包，更新点集$V$的答案。

对于距离限制，只需要将点集$V$按能更新它的深度从大到小排序，按需建凸包即可

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
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 200005, INF = 1e9;
typedef long long ll;

char buf[1 << 20], *p1, *p2;
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
inline ll _R() {
	ll d = 0; char t; bool ty = 1;
	while (t = GC, (t < '0' || t > '9') && t != '-');
	t == '-' ? (ty = 0) : (d = t - '0');
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return ty ? d : -d;
}

int n, f[N], sz[N];
ll p[N], q[N], nl[N], dis[N], ans[N];
int Tote, Last[N], End[N], Next[N];
ll Len[N];
inline void ADDE(int x, int y, ll z) {
	End[++ Tote] = y, Next[Tote] = Last[x], Last[x] = Tote, Len[Tote] = z;
}

void dfs_init(int x) {
	for (int i = Last[x], u; u = End[i], i; i = Next[i])
		dis[u] = dis[x] + Len[i], dfs_init(u);
}

int minn;
bool vis[N];
void getrt(int x, int tot, int& rt) {
	int maxx = 0; sz[x] = 1;
	for (int i = Last[x], u; i; i = Next[i])
		if (u = End[i], !vis[u]) getrt(u, tot, rt), maxx = max(maxx, sz[u]), sz[x] += sz[u];
	maxx = max(maxx, tot - sz[x]);
	if (maxx < minn && sz[x] > 1) rt = x, minn = maxx;
}

int cnt;
struct Data { ll val; int id; } A[N];
bool operator < (const Data& lhs, const Data& rhs) { return lhs.val > rhs.val; }

void getdata(int x) {
	cnt ++;
	A[cnt].val = dis[x] - nl[x], A[cnt].id = x;
	for (int i = Last[x], u; i; i = Next[i])
		if (u = End[i], !vis[u]) getdata(u);
}

int s[N];
double slope(int x, int y) {
	return (double) (ans[x] - ans[y]) / (double) (dis[x] - dis[y]);
}
void DC(int x, int tot) {
	if (tot == 1) return;
	int i, j, k, rt; minn = INF, getrt(x, tot, rt);
	for (i = Last[rt]; i; i = Next[i]) vis[End[i]] = 1;
	DC(x, tot - sz[rt] + 1);
	cnt = 0;
	for (i = Last[rt]; i; i = Next[i]) getdata(End[i]);
	sort(A + 1, A + 1 + cnt);
	int l, r, mid, key, top = 0, now = rt;
	for (i = 1; i <= cnt; i ++) {
		while (now != f[x] && A[i].val <= dis[now]) {
			while (top > 1 && slope(s[top], s[top - 1]) <= slope(now, s[top])) top --;
			s[++ top] = now, now = f[now];
		}
		if (!top) continue;
		l = 1, r = top - 1, key = 1, k = A[i].id;
		while (l <= r) {
			mid = l + r >> 1;
			if (slope(s[mid], s[mid + 1]) >= p[k]) key = mid + 1, l = mid + 1;
			else r = mid - 1;
		}
		ans[k] = min(ans[k], p[k] * (dis[k] - dis[s[key]]) + q[k] + ans[s[key]]);
	}
	for (i = Last[rt]; i; i = Next[i]) DC(End[i], sz[End[i]]);
}

int main() {
	int i, j, k;
	n = _R(), _R();
	for (i = 2; i <= n; i ++) {
		f[i] = _R(), ADDE(f[i], i, _R());
		p[i] = _R(), q[i] = _R(), nl[i] = _R();
	}
	dfs_init(1);
	fill(ans + 2, ans + 1 + n, 9e18);
	DC(1, n);
	for (i = 2; i <= n; i ++) printf("%lld\n", ans[i]);
}