NOI2014 购票

Vexoben

Feb 22, 2019

It takes 10 minutes to read this article.

题目链接： NOI2014 购票

(刷新以获取数学公式)

题意

给定一棵 $n$ 个结点的树,边有边权,每个结点有三个权值 $l_i$ , $u_i$ , $v_i$ .从一个点出发可以跳到它距离不超过 $l_i$ 的祖先.设跳跃距离为 $d$ ,付出的代价就是 $p_u*d + q_u$ .求每个点到根结点的最小代价.

数据范围: $n≤200000$

题解

设点 $i$ 到根的距离为 $dis_i$ ,显然可以列出 $O(n^2)$ 的转移方程:

$dp_u = min_{v} (dis_u-dis_v)*p_u + q_u + dp_v$

其中要求 $v$ 是 $u$ 的祖先,且 $dis_u-dis_v≤l_u$

移项之后可以得到:

$dp_u = min_{v} (-p_u*dis_v+dp_v)+p_u*dis_u+q_u$

忽略常数 $p_u*dis_u+q_u$ ,我们要求最小化的是:

$f(v) = -p_u*dis_v+dp_v$

令 $b=f(v)$ , $k=p_u$ , $x=dis_v$ , $y=dp_v$ ,原式就被改写为: $b=-kx+y$ ,即 $y=kx+b$

在这里 $k$ 是定值,确定一个 $(dis_v,dp_v)$ ,就相当于确定了一条斜率为 $k$ ,且过点 $dis_v,dp_v$ 的直线,我们要求的是其中截距最小的一条.

先无视 $l_i$ 的限制,并假设树是一条链.

我们发现,所有可能用来转移的点一定形成了一个下凸壳.

先直观感受一下,如果是一段弧线,最优的点一定使得直线和弧线相切.

而如果是一个凸包,最优点一定在它与下一个点形成的直线的斜率刚好大于 $k$ 的那个点.

因此我们可以维护这个凸包,每次二分出这个转移点进行转移,复杂度就是 $O(nlogn)$ 的.

怎么处理 $dis_u-dis_v≤l_u$ 的限制呢?cdq分治!

计算 $[l,r]$ 时,先分治计算 $[l,mid]$ ,然后考虑 $[l,mid]$ 对 $[mid+1,r]$ 的影响.将[mid+1,r]中的点关于 $dis_u-l_u$ 排序, $[l,mid]$ 中的点依次加入凸包,在适当的时候计算一下贡献.然后递归计算 $[mid+1,r]$ .类似的题可以看下NOI2007货币兑换Cash

那么怎么对付树形结构呢?点分治!

当前中心假设是 $G$ ,先递归计算带有根节点的那棵子树.然后提取出 $G$ 到根节点的路径,用他们更新一边其余的点,然后对其它子树分别计算即可.

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const LL inf = 0x3f3f3f3f;

template <typename T> void read (T &x) {
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + c - '0';
}

int n, t, E, tot, G, G_siz;
int fir[N], nex[N << 1], arr[N << 1];
int fa[N], siz[N], vis[N];
LL l[N], s[N], p[N], q[N], dp[N], dis[N], px[N], py[N], top[N];
vector<int> vec;

inline void Add_Edge(int x, int y) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y;
}

void get_size(int x, int fa, int type) {
	siz[x] = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa || vis[arr[i]]) continue;
		get_size(arr[i], x, type);
		siz[x] += siz[arr[i]];
	}
	if (type) vec.push_back(x);
}

void find_G(int x, int fa, int totsize) {
	int max_son = 0;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa || vis[arr[i]]) continue;
		find_G(arr[i], x, totsize);
		max_son = max(max_son, siz[arr[i]]);
	}
	int tmp = max(max_son, totsize - siz[x]);
	if (tmp < G_siz) {
		G = x;
		G_siz = tmp;
	}
}

bool cmp(int x, int y) {
	return (top[x] > top[y]);
}

double slope(LL x1, LL y1, LL x2, LL y2) {
	return 1.0 * (y1 - y2) / (x1 - x2);
}

void ins(LL x, LL y) {
	while (tot > 1) {
		double k1 = slope(px[tot - 1], py[tot - 1], x, y);
		double k2 = slope(px[tot], py[tot], x, y);
		if (k1 <= k2) --tot;
		else break;
	}
	++tot;
	px[tot] = x; py[tot] = y;
}

void Solve(int x) {
	vis[x] = 1;
	vector<int> anc;
	anc.push_back(x);
	int t = fa[x];
	while (!vis[t] && t) {
		anc.push_back(t);
		t = fa[t];
	}
	for (int i = fir[x]; i; i = nex[i]) {
		if (dis[arr[i]] < dis[x] && !vis[arr[i]]) {
			G = 0;
			G_siz = inf;
			get_size(arr[i], x, 0);
			find_G(arr[i], x, siz[arr[i]]);
			Solve(G);
		}
	}
	for (int i = 1; i < anc.size(); ++i) {
		int v = anc[i];
		if (top[x] > dis[v]) break;
		dp[x] = min(dp[x], (dis[x] - dis[v]) * p[x] + q[x] + dp[v]);
	}
	vec.clear();
	for (int i = fir[x]; i; i = nex[i]) {
		if (dis[arr[i]] > dis[x] && !vis[arr[i]]) {
			get_size(arr[i], x, 1);
		}
	}
	sort(vec.begin(), vec.end(), cmp);
	tot = 0;
	for (int i = 0, j = -1; i < vec.size(); ++i) {
		int t = vec[i];
		if (top[t] > dis[x]) continue;
		while (j + 1 < anc.size() && top[t] <= dis[anc[j + 1]]) {
			++j;
			ins(dis[anc[j]], dp[anc[j]]);
		}
		LL k = p[t];
		int l = 1, r = tot, ans = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			double slp;
			if (mid == tot) slp = -1e18;
			else slp = slope(px[mid], py[mid], px[mid + 1], py[mid + 1]);
			if (slp <= k) {
				ans = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		dp[t] = min(dp[t], -k * px[ans] + py[ans] + dis[t] * p[t] + q[t]);
	}
	vector<int>().swap(anc);
	vector<int>().swap(vec);
	for (int i = fir[x]; i; i = nex[i]) {
		if (dis[arr[i]] > dis[x] && !vis[arr[i]]) {
			G = 0;
			G_siz = inf;
			find_G(arr[i], x, siz[arr[i]]);
			Solve(G);
		}
	}
}

int main() {
	read(n); read(t);
	for (int i = 2; i <= n; ++i) {
		LL f, s;
		read(f); read(s);
		dis[i] = dis[f] + s;
		Add_Edge(f, i);
		Add_Edge(i, f);
		read(p[i]); read(q[i]); read(l[i]);
		top[i] = dis[i] - l[i]; fa[i] = f;
	}
	for (int i = 2; i <= n; ++i) dp[i] = 1e18;
	G_siz = inf;
	get_size(1, 0, 0);
	find_G(1, 0, n);
	Solve(G);
	for (int i = 2; i <= n; ++i) printf("%lld\n", dp[i]);
	return 0;
}