打字

· · 题解

首先我们类似题意建字典树，设 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;
}