LG10333 [UESTCPC 2024] 打字 题解
给定一颗 \(n\) 个节点的 trie 树，以 \(1\) 号节点为根，其余每个节点到父亲的边上都有一个字符，且父亲相同的节点到父亲的边上的字符互不相同。从根到每个节点的路径都代表一个单词，这个单词由路径上的字符顺序拼接而成。在每个节点 \(i\) 处有一个权值 \(c_i\)，表示该节点所代表的单词需要写出的次数。
你有一个 cache，可以选择任意个单词放在 cache 里面。写单词时，每写一个字符需要花费 \(a\) 的代价。当写出一个完整的单词时，就可以选择结束当前单词，转而拼写下一个单词。而 cache 会根据当前已经写出的字符，把 cache 中以这一部分字符为前缀且字典序最小的单词提示出来。此时你可以花费 \(b\) 的代价直接写出这个单词，并结束当前单词的拼写，转而拼写下一个单词。注意一个字符串本身也看作它自己的前缀。
求完成 trie 树上所有单词的拼写所需的最小代价。
几乎全部参考这篇题解，主要是好久没写李超树和这种斜率的题了，于是单独开一篇记录一下。
首先还是要读懂题目（这个入一开始就没读懂）。这个的意思不是说拼写完成一个单词后可以根据这个单词提示，而是，每次单词的拼写是独立的，只不过拼写一个单词的过程中，可以先花费 \(a\times len\) 写一段前缀，再花费 \(b\) 直接提示出来。
还是正难则反：如果不使用 cache，总花费是 \(a\times c_i\times dep_i\)；考虑怎样使用 cache 减少尽可能多的花费。
假设已经选定好了 cache，将 cache 中的字符串按字典序排好并标号（这个顺序显然也等价于 dfs 序），设第 \(i\) 个字符串对应 trie 树上的节点为 \(u(i)\)，则对于第 \(i\) 个字符串减少的花费为
可以写成转移的形式，便于形成字符串按字典序依次转移的印象
假设当前我们将点 \(u\) 加入 cache，需要从 dfs 序小于 \(u\) 的点 \(v\) 转移过来。
考虑去掉 \(\text{lca}\)，令 \(f\) 为点 \(u\) 的一个祖先，\(g_f=\max_{\text{lca}(u,v)=f} dp_v\)，自然有
这个 \(g_f\) 的定义看起来很唬人，但实际上你会发现这相当于遍历整棵 trie 树时，每个 \(f\) 完全访问过的子树中节点 \(dp\) 的 \(\max\)，即包含当前点 \(u\) 的子树和 dfs 序在之后的子树不包括在内。
然后对于这个式子就可以写成直线的形式
每次当 \(g_f\) 的值有更新时将 \(y=-(dep_f+1)c_ux+g_f\) 这条直线加入李超线段树，查询 \(c_u\) 时的最大值即可。
可能会有疑问，当一个点 \(v\) 不是 \(u\) 的祖先时，我们也会查询到 \(v\) 对应的直线。但这并不影响，因为 \(f=\text{lca(u,v)}\) 一定也会在李超树中，且 \(g_f\geq g_v,dep_f<dep_v\)，一定会优先取到 \(f\)。
具体实现见代码。
const int R=10000;
int n;
ll A,B,c[N],dp[N],g[N],ans;
int dep[N];
vector<int>tar[N];
struct sgline{ll k,b;
}lin[N];int tot;
int bel[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
inline ll hei(int id,ll L){return lin[id].k*L+lin[id].b;}
void modify(int p,int l,int r,int id){if(hei(id,mid)>hei(bel[p],mid))swap(bel[p],id);if(hei(id,l)>hei(bel[p],l))modify(ls,l,mid,id);if(hei(id,r)>hei(bel[p],r))modify(rs,mid+1,r,id);
}
void update(int p,int l,int r,int L,int R,int id){if(L<=l&&r<=R)return modify(p,l,r,id),void();if(L<=mid)update(ls,l,mid,L,R,id);if(R>mid)update(rs,mid+1,r,L,R,id);
}ll query(int p,int l,int r,int L){ll tmp=hei(bel[p],L);if(l==r)return tmp;if(L<=mid)tmp=max(tmp,query(ls,l,mid,L));else tmp=max(tmp,query(rs,mid+1,r,L));return tmp;
}
inline void add(ll k,ll b){lin[++tot].k=k;lin[tot].b=b;modify(1,0,R,tot);
}void dfs(int u){dp[u]=query(1,0,R,c[u])+dep[u]*A*c[u]-B*c[u];g[u]=dp[u];//子树maxadd(-(dep[u]+1)*A,g[u]);for(auto v:tar[u]){dep[v]=dep[u]+1;dfs(v);if(g[v]>g[u]){g[u]=g[v];add(-(dep[u]+1)*A,g[u]);}}
}int main(){scanf("%d%lld%lld",&n,&A,&B);for(int i=1;i<=n;++i){scanf("%lld",&c[i]);int x;scanf("%d",&x);for(int j=1;j<=x;++j){int v;scanf("%d",&v);tar[i].push_back(v);}}dep[1]=0;dfs(1);for(int i=2;i<=n;++i){ans+=A*dep[i]*c[i];}ans-=g[1];printf("%lld\n",ans);return 0;
}