自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 23:06:36，当前版本为作者最后更新于2025-06-02 21:33:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

给定一棵 $n$ 个点的树，边有边权。有一个 $n$ 个点的有向完全图，$i \to j$ 边权为 $a_i + \operatorname{dis}(i, j) \times b_i$。对于所有 $2 \le i \le n$，求 $1 \rightsquigarrow i$ 的最短路。

$2 \le n \le 10^5$，2s，1G。

---

性质：最短路除了终点的其他点 $b_i$ 递减。

考虑 DP，设 $f_u$ 为 $1 \rightsquigarrow u$ 且路径所有点 $b_u$ 递减的最短路长度，有：

$$f_u = \min\limits_{b_v > b_u} f_v + a_v + \operatorname{dis}(u, v) \times b_v $$

再设 $g_u$ 为 $1 \rightsquigarrow u$ 的最短路长度，有：

$$g_u = \min\limits_{v} f_v + a_v + \operatorname{dis}(u, v) \times b_v $$

看到树上距离考虑点分治。

点分树上每个点 $u$ 维护子树内 $(-b_v, f_v + a_v + \operatorname{dis}(u, v) \times b_v)$ 的凸包。由于 $b_v$ 有序所以凸包可以用支持 pop_back 的 vector 维护。

算 $f_u$ 就枚举 $u$ 在点分树上的祖先 $v$，相当于查询斜率为 $\operatorname{dis}(u, v)$ 的直线与凸包的最大截距。二分即可。

算 $g_u$ 可以用同样的方法。

时间复杂度 $O(n \log^2 n)$，空间复杂度 $O(n \log n)$。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;
const int logn = 20;

ll n, a[maxn], b[maxn], dep[maxn], f[maxn], h[maxn];
int st[logn][maxn], dfn[maxn], tim;
vector<pii> G[maxn];
vector<int> T[maxn];

inline int get(int i, int j) {
	return dfn[i] < dfn[j] ? i : j;
}

inline int qlca(int x, int y) {
	if (x == y) {
		return x;
	}
	x = dfn[x];
	y = dfn[y];
	if (x > y) {
		swap(x, y);
	}
	++x;
	int k = __lg(y - x + 1);
	return get(st[k][x], st[k][y - (1 << k) + 1]);
}

inline ll qdis(int x, int y) {
	return dep[x] + dep[y] - dep[qlca(x, y)] * 2;
}

void dfs(int u, int t) {
	dfn[u] = ++tim;
	st[0][tim] = t;
	for (pii p : G[u]) {
		ll v = p.fst, d = p.scd;
		if (v == t) {
			continue;
		}
		dep[v] = dep[u] + d;
		dfs(v, u);
	}
}

struct node {
	ll x, y;
	node(ll a = 0, ll b = 0) : x(a), y(b) {}
};

inline node operator + (const node &a, const node &b) {
	return node(a.x + b.x, a.y + b.y);
}

inline node operator - (const node &a, const node &b) {
	return node(a.x - b.x, a.y - b.y);
}

inline lll operator * (const node &a, const node &b) {
	return (lll)a.x * b.y - (lll)a.y * b.x;
}

int rt, g[maxn], sz[maxn], fa[maxn], p[maxn];
bool vis[maxn];

void dfs2(int u, int fa, int t) {
	sz[u] = 1;
	g[u] = 0;
	for (pii p : G[u]) {
		int v = p.fst;
		if (v == fa || vis[v]) {
			continue;
		}
		dfs2(v, u, t);
		sz[u] += sz[v];
		g[u] = max(g[u], sz[v]);
	}
	g[u] = max(g[u], t - sz[u]);
	if (!rt || g[u] < g[rt]) {
		rt = u;
	}
}

void dfs3(int u) {
	vis[u] = 1;
	for (pii p : G[u]) {
		int v = p.fst;
		if (vis[v]) {
			continue;
		}
		rt = 0;
		dfs2(v, u, sz[v]);
		dfs2(rt, u, sz[v]);
		fa[rt] = u;
		T[u].pb(rt);
		dfs3(rt);
	}
}

vector<node> S[maxn];
node c[maxn];
int stk[maxn], top, tot, pt[maxn], K;
ll e[maxn];

void dfs5(int u, int fa, ll d) {
	c[++tot] = node(-b[u], f[u] + a[u] + b[u] * d);
	e[u] = d;
	pt[++K] = u;
	for (pii p : G[u]) {
		ll v = p.fst, k = p.scd;
		if (v == fa || vis[v]) {
			continue;
		}
		dfs5(v, u, d + k);
	}
}

inline void work(int u) {
	tot = 0;
	K = 0;
	dfs5(u, -1, 0);
	sort(c + 1, c + tot + 1, [&](const node &a, const node &b) {
		return a.x < b.x || (a.x == b.x && a.y < b.y);
	});
	top = 0;
	for (int i = 1; i <= tot; ++i) {
		while (top >= 2 && (c[i] - c[stk[top - 1]]) * (c[stk[top]] - c[stk[top - 1]]) >= 0) {
			--top;
		}
		stk[++top] = i;
	}
	tot = top;
	for (int i = 1; i <= tot; ++i) {
		c[i] = c[stk[i]];
	}
	for (int i = 1; i <= K; ++i) {
		int v = pt[i], l = 2, r = tot, p = 1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (c[mid].y - c[mid - 1].y <= (c[mid].x - c[mid - 1].x) * e[v]) {
				p = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		h[v] = min(h[v], c[p].y - c[p].x * e[v]);
	}
}

void dfs4(int u) {
	vis[u] = 1;
	work(u);
	for (int v : T[u]) {
		dfs4(v);
	}
}

vector<ll> travel(vector<ll> _a, vector<int> _b, vector<int> _u, vector<int> _v, vector<int> _w) {
	n = (int)_a.size();
	for (int i = 1; i <= n; ++i) {
		a[i] = _a[i - 1];
		b[i] = _b[i - 1];
	}
	for (int i = 0; i < n - 1; ++i) {
		int u = _u[i] + 1, v = _v[i] + 1, d = _w[i];
		G[u].pb(v, d);
		G[v].pb(u, d);
	}
	dfs(1, -1);
	for (int j = 1; (1 << j) <= n; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
			st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}
	dfs2(1, -1, n);
	int x = rt;
	dfs2(x, -1, n);
	dfs3(x);
	for (int i = 1; i <= n; ++i) {
		p[i] = i;
	}
	sort(p + 2, p + n + 1, [&](const int &x, const int &y) {
		return b[x] > b[y];
	});
	mems(f, 0x3f);
	for (int i = 1; i <= n; ++i) {
		int u = p[i];
		if (i > 1 && b[u] > b[1]) {
			continue;
		}
		if (i == 1) {
			f[u] = 0;
		} else {
			for (int v = u; v; v = fa[v]) {
				if (S[v].empty()) {
					continue;
				}
				int l = 1, r = (int)S[v].size() - 1, p = 0;
				ll k = qdis(u, v);
				while (l <= r) {
					int mid = (l + r) >> 1;
					if (S[v][mid].y - S[v][mid - 1].y <= (S[v][mid].x - S[v][mid - 1].x) * k) {
						p = mid;
						l = mid + 1;
					} else {
						r = mid - 1;
					}
				}
				f[u] = min(f[u], S[v][p].y - S[v][p].x * k);
			}
		}
		for (int v = u; v; v = fa[v]) {
			node w(-b[u], f[u] + a[u] + b[u] * qdis(u, v));
			while ((int)S[v].size() >= 2 && (w - S[v][(int)S[v].size() - 2]) * (S[v].back() - S[v][(int)S[v].size() - 2]) >= 0) {
				S[v].pop_back();
			}
			S[v].pb(w);
		}
	}
	mems(h, 0x3f);
	mems(vis, 0);
	dfs4(x);
	vector<ll> vc;
	for (int i = 2; i <= n; ++i) {
		vc.pb(h[i]);
	}
	return vc;
}

// int main() {
	// int n;
	// scanf("%d", &n);
	// vector<ll> a(n);
	// vector<int> b(n);
	// for (ll &x : a) {
		// scanf("%lld", &x);
	// }
	// for (int &x : b) {
		// scanf("%d", &x);
	// }
	// vector<int> u(n - 1), v(n - 1), w(n - 1);
	// for (int i = 0; i < n - 1; ++i) {
		// scanf("%d%d%d", &u[i], &v[i], &w[i]);
	// }
	// auto ans = travel(a, b, u, v, w);
	// for (ll x : ans) {
		// printf("%lld\n", x);
	// }
	// return 0;
// }