自动搬运

查看原文

来自洛谷，原作者为

	zhongpeilin **

搬运于2025-08-24 22:57:01，当前版本为作者最后更新于2024-06-04 20:04:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先我们类似题意建字典树，设 $dis_{u}$ 表示 u 节点的深度。

那么我们发现正着搞不好搞，那么先将答案设为 $\sum_{i = 1}^{n} dis_{i} \times A \times c_{i}$，你会发现假设 $id_{1}, id_{2} \dots id_{len}$ 是 cache 中的字符串编号按字典树顺序排序，那么答案会少 $\sum_{i = 1}^{len} ((dis_{id_{i}} - dis_{LCA(id_{i - 1}, id_{i})} - 1) \times A - B) \times c_{id_{i}}$，其中我们设 $dis_{id_{1}} - LCA_{id_{0}, id_{1}} - 1 = 0$，因为第一个单词只需打一个 $B \times c_{id_{1}}$。

所以设 $dp_{x}$ 表示 dfn 序列中在 $x$ 及之前的能减去的最大答案，这里强制 $x$ 放入 cache。

那么枚举上一个放入 cache 的单词，假设标号为 $y$，则：

$$dp_{x} = \max_{dfn 中 y 在 x 前面} (dp_{y} + ((dis_{x} - dis_{LCA_{x, y}} - 1) \times A - B) \times c_{x}) $$

你会发现 $dis_{LCA_{x, y}}$ 很难受，那么设 $f_{x}$ 表示当前 $x$ 子树中 dp 最大的值，那么转移变成了枚举 LCA，有：

$$dp_{x} = \max_{y 是 x 祖宗} (f_{y} + ((dis_{x} - dis_{y} - 1) \times A - B) \times c_{x}) $$

那么拆一下：

$$dp_{x} = \max_{y 是 x 祖宗} (f_{y} + (dis_{x} \times A - {dis_{y} + 1} \times A - B) \times c_{x}) $$

所以：

$$dp_{x} = \max_{y 是 x 祖宗} (f_{y} + dis_{x} \times A \times c_{x} - (dis_{y} + 1) \times A \times c_{x}- B \times c_{x}) $$$$dp_{x} = \max_{y 是 x 祖宗} (f_{y} - (dis_{y} + 1) \times A \times c_{x}) - B \times c_{x} + dis_{x} \times A \times c_{x} $$

将一次函数中 $k$ 看成 $-(dis_{y} + 1) \times A \times c_{x}$, $b$ 看成 $f_{y}$，建李超树。

CODE：

using namespace std;
#define int long long
struct Segment{
	int k, b;
}a[800005];
int tree[800005], tot, ans;
int n, A, B, c[200005], dp[200005], dis[200005];
vector<int> g[200005];

void dfs(int x){
	ans += c[x] * A * dis[x];
	for(auto it : g[x]){
		dis[it] = dis[x] + 1;
		dfs(it);
	}
}
int GET(int id, int x){
	return a[id].k * x + a[id].b;
}

int query(int u, int l, int r, int pos){
	if(l == r) return GET(tree[u], l);
	int mid = (l + r) / 2;
	if(pos <= mid) return max(GET(tree[u], pos), query(u << 1, l, mid, pos));
	else return max(GET(tree[u], pos), query(u << 1 | 1, mid + 1, r, pos));
}

void add(int u, int l, int r, int id){
	if(!id) return ;
	int mid = (l + r) / 2;
	if(GET(id, mid) > GET(tree[u], mid) || !tree[u]) swap(id, tree[u]);
	if(l == r) return ;
	if(GET(id, l) > GET(tree[u], l)) add(u << 1, l, mid, id);
	if(GET(id, r) > GET(tree[u], r)) add(u << 1 | 1, mid + 1, r, id);
}

void addedge(int x){
	a[++tot] = {-1 * (dis[x] + 1) * A, dp[x]};
	add(1, 0, 10000, tot);
}
void DP(int x){
	dp[x] = query(1, 0, 10000, c[x]) - B * c[x] + dis[x] * A * c[x];
	addedge(x);
	cout << dp[x] << endl;
	for(auto it : g[x]){
		DP(it);
		if(dp[it] > dp[x]){
			dp[x] = dp[it];
			addedge(x);
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> A >> B;
	for(int i = 1; i <= n; i++){
		int k;
		cin >> c[i] >> k;
		for(int j = 1; j <= k; j++){
			int son;
			cin >> son;
			g[i].push_back(son);
		}
	}
	dfs(1);
	DP(1);
	cout << ans - dp[1] << endl;
	return 0;
}