题目：洛谷P2305、LOJ#2249

题目描述：

给定一棵\(n\)个点的树，根为\(1\)，树上每条边的长度已知，从每个点\(x\)到根的方法为：选择一个祖先\(a\)，到达它需要消耗的代价为\(dis_{x,a} \cdot p_{x} + q_{x}\)，然后依次往上，直到到达根，其中\(dis_{x,y}\)表示的是树上两点\(x,y\)之间的距离，\(p,q\)均为题目给定的参数，同时还给定了一个限制，就是点\(x\)往上跳祖先，不能直接跳到与他距离超过\(limit_{x}\)的祖先，请你求出每个点到达根的最小代价

\(n \leq 2 \cdot 10^{5}\)，保证答案不超过\(longlong\)范围

蒟蒻题解：

记\(dep[x]\)为点\(x\)在树上的深度

很容易推出裸的\(dp\)方程：

\[f[i] = f[j] + p[i] \cdot (dep[i] - dep[j]) + q[i] \]

发现它有的项既有\(i\)又有\(j\)，考虑斜率优化，将式子转换成：

\[f[j] = p[i] \cdot dep[j] + (f[i] - p[i] \cdot dep[i] - q[i]) \]

其中\(y = f[j], x = dep[j], k = p[i], b = f[i] - p[i] \cdot dep[i] - q[i]\)

那么这题如果不考虑限制\(l_{x}\)的话，就是斜率优化维护一个下凸包+二分+单调栈就可以了

那么加上限制\(limit_{x}\)呢？

如果在把凸包前面不满足限制的一段删掉，会出现下面这种情况：

如图，红点在斜率优化过程中被删除，蓝线是限制\(limit_{x}\)，所以在限制\(limit_{x}\)的条件下，红点可能是合法的，不应该被删除

树上问题是由一条一条链拼起来的，先以链上问题思考，我们可以CDQ分治，把这条链分成两段，计算上方对下方的影响，至于拆成多段，我们可以考虑点分治

具体来讲，我们当前的根为\(x\)，找出当前子树重心\(y\)，计算\(x子树\)除去\(y\)下方所有节点的答案，然后再CDQ分治计算\(y\)及\(y\)上方的答案对\(y\)下方的影响

我们把\(y\)下方的所有点取出来，按\(dep_{i}-limit_{i}\)从大到小排序，然后对于\(x\)到\(y\)上的点，按深度从大到小加入凸包内，然后在凸包上二分计算答案

CDQ分治主要体现在思想，算法以点分治+二分为主，时间复杂度是\(\theta(n\ log^{2}n)\)

注意：

• 斜率优化时，如果不计算斜率，而是叉乘的话会爆\(longlong\)
• 点分治找重心时，如果有多个重心，且根为其中一个重心，应取根为重心，不然会死循环（例如根为\(x\)，且仅有\(x->y\)一条边，重心为\(y\)，每次操作都是删去重心的孩子，所以它会一直保留\(x\)，又保留\(y\)，就会导致死循环）

参考程序：

#include<bits/stdc++.h>
using namespace std;
#define Re register int
typedef long long ll;
typedef double dl;

const int N = 200005;
const dl eps = 1e-6;
const ll Inf = 2e18;
int n, rt, mn, cnt, h, t, res, a[N], qu[N], fa[N], p[N], siz[N], mx[N], hea[N], nxt[N], to[N];
ll len[N], q[N], lt[N], dep[N], f[N];
bool b[N];

inline ll read()
{
	char c = getchar();
	ll ans = 0;
	while (c < 48 || c > 57) c = getchar();
	while (c >= 48 && c <= 57) ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar();
	return ans;
}

inline void write(ll x)
{
	int num = 0;
	char sc[25];
	if (!x) sc[num = 1] = 48;
	while (x) sc[++num] = x % 10 + 48, x /= 10;
	while (num) putchar(sc[num--]);
	putchar('\n');
}

inline int max(int x, int y)
{
	return x > y ? x : y;
}

inline ll min(ll x, ll y)
{
	return x < y ? x : y;
}

inline void add(int x, int y)
{
	nxt[++cnt] = hea[x], to[cnt] = y, hea[x] = cnt;
}

inline void dfs(int x)
{
	for (Re i = hea[x]; i; i = nxt[i])
	{
		int u = to[i];
		dep[u] = dep[x] + len[u];
		dfs(u);
	}
}

inline void find_root(int x, int y)
{
	siz[x] = 1, mx[x] = 0;
	for (Re i = hea[x]; i; i = nxt[i])
	{
		int u = to[i];
		if (b[u]) continue;
		find_root(u, y);
		siz[x] += siz[u], mx[x] = max(mx[x], siz[u]);
	}
	mx[x] = max(mx[x], y - siz[x]);
	if (mx[x] <= mn) mn = mx[x], rt = x;//是<=，不是<
}

inline void dfs2(int x)
{
	a[++res] = x;
	for (Re i = hea[x]; i; i = nxt[i])
		if (!b[to[i]]) dfs2(to[i]);
}

inline bool cmp(int x, int y)
{
	return dep[x] - lt[x] > dep[y] - lt[y];
}

inline ll que(int x)
{
	int l = h + 1, r = t, s = h;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (((dl)f[qu[mid]] - f[qu[mid - 1]]) / ((dl)dep[qu[mid]] - dep[qu[mid - 1]] + eps) >= p[x]) s = mid, l = mid + 1;
		else r = mid - 1;
	}
	return f[qu[s]] - dep[qu[s]] * p[x] + dep[x] * p[x] + q[x];
}

inline void dfs1(int x, int y)
{
	if (y == 1) return;
	mn = n;
	find_root(x, y);
	int z = rt;
	for (Re i = hea[z]; i; i = nxt[i]) b[to[i]] = 1, y -= siz[to[i]];
	dfs1(x, y);
	res = 0;
	for (Re i = hea[z]; i; i = nxt[i]) dfs2(to[i]);
	sort(a + 1, a + res + 1, cmp);
	h = 0, t = -1;
	for (Re i = 1, j = z; i <= res; ++i)
	{
		while (j ^ fa[x] && dep[j] >= dep[a[i]] - lt[a[i]])
		{
			while (h < t && ((dl)f[qu[t]] - f[qu[t - 1]]) / ((dl)dep[qu[t]] - dep[qu[t - 1]] + eps) <= ((dl)f[j] - f[qu[t]]) / ((dl)dep[j] - dep[qu[t]] + eps)) --t;
			qu[++t] = j, j = fa[j];
		}
		if (h <= t) f[a[i]] = min(f[a[i]], que(a[i]));
	}
	for (Re i = hea[z]; i; i = nxt[i]) dfs1(to[i], siz[to[i]]);
}

int main()
{
	n = read(), mn = read();
	for (Re i = 2; i <= n; ++i)
	{
		fa[i] = read(), len[i] = read(), p[i] = read(), q[i] = read(), lt[i] = read(), f[i] = Inf;
		add(fa[i], i);
	}
	dfs(1), dfs1(1, n);
	for (Re i = 2; i <= n; ++i) write(f[i]);
	return 0;
}