题目链接:
题解: 显然答案一定小于\(n\times n\), 字符串倒过来变成前缀建Trie, 题意转化如下:
每次可以在一棵树上标记一个点，要求标记一个点之前所有祖先都标记过，标记一个点的价值等于它父亲被标记的时间，最大化价值和(也可以是求所有父子标记时间之差的和的最小值)
一看到这个脑子里立刻蹦出一个贪心: 按照儿子个数从小到大选(用堆维护)
然而是错的
hack数据:
10aaabaacaadaaeaaaaababbb
正确的方案是按子树大小从小到大选。这里提供一个不知道对不对的证明(其实是拼凑网上的其他题解):
(1) 最优答案一定是DFS序。这个按照父子时间差之和来理解，挺显然。(抱歉我水平有限也就能说到这个份上了……)
(2) DFS序中的最优答案一定是按子树大小从小到大选。感性理解是: 由于是DFS序我们可以只考虑根对答案产生的贡献，最小化根与其所有儿子的时间差之和。然后就相当于有一堆数给他们排序使得前缀和的和最小，然后就显然了……
教训: 贪心这种东西千万不能想当然，一定要证明！要证明！要证明！
代码
#include#include #include #include #define llong long longusing namespace std;const int N = 1e5;const int L = 5e5+1e4;const int S = 26;struct Edge{ int v,nxt;} e[(N<<1)+3];int son[L+3][S+1];char str[L+3];bool isky[L+3];int sz[N+3];int sonn[N+3];int fe[N+3];int fa[N+3];struct Element{ int u; Element() {} Element(int _u) {u = _u;} bool operator <(const Element &arg) const { return sz[u]>sz[arg.u]; }};priority_queue que;int n,siz,nn,en;void insertstr(char str[],int len){ int u = 1; for(int i=1; i<=len; i++) { if(!son[u][str[i]]) {siz++; son[u][str[i]] = siz;} u = son[u][str[i]]; } isky[u] = true;}void addedge(int u,int v){ printf("addedge %d %d\n",u,v); en++; e[en].v = v; e[en].nxt = fe[u]; fe[u] = en;}void dfs0(int u,int anc){ if(isky[u]) {nn++; addedge(nn,anc); addedge(anc,nn); sonn[anc]++; anc = nn;} for(int i=1; i<=S; i++) { int v = son[u][i]; if(v) { dfs0(v,anc); } }}void dfs(int u){ sz[u] = 1; for(int i=fe[u]; i; i=e[i].nxt) { if(e[i].v==fa[u]) continue; fa[e[i].v] = u; dfs(e[i].v); sz[u] += sz[e[i].v]; }}int main(){ siz = 1; scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%s",str+1); int len = strlen(str+1); for(int j=1; j<=len; j++) str[j] -= 96; for(int j=1; j<=len+1-j; j++) swap(str[j],str[len+1-j]); insertstr(str,len); } nn = 1; dfs0(1,1); dfs(1); que.push(Element(1)); llong ans = 0ll; for(int i=1; i<=nn; i++) { int u = que.top().u; que.pop(); printf("%d\n",u); ans += sonn[u]*(i-1ll); for(int j=fe[u]; j; j=e[j].nxt) { if(e[j].v==fa[u]) continue; fa[e[j].v] = u; que.push(e[j].v); } } ans = n*(n+1ll)/2ll-ans; printf("%lld\n",ans); return 0;}