#P8679. [2019年省队联测]地

    ID: 8766 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>字符串后缀数组字符串哈希图论CF3000最小生成树DFSBFS

[2019年省队联测]地

地 ( floor.cpp )

题目背景

幻想乡地铁修建计划2.0

题目描述

幻想乡有nn 个重要城镇,每个城镇有官方名称AiA_{i} 和民间名称BiB_{i}。乡长想在幻想乡修一些地铁,使得两两城镇之间都可以通过地铁互相到达,且修的地铁尽量少。在两个城镇i,ji , j之间修的地铁的和谐度 $w=\operatorname{LCP} ( A_{i} , B_{j} )+\operatorname{LCP} ( B_{i} , A_{j} )$。乡长希望你帮助他求出地铁线路和谐度之和最大的方案。你只需要输出最大的和谐度是多少。

LCP⁡(X,Y)\operatorname{LCP}(X,Y) 表示字符串 X,YX,Y 的最长公共前缀长度。

输入格式

第一行一个正整数 nn。

接下来 nn 行,每行一个字符串 AiA_i;再接下来 nn 行,每行一个字符串 BiB_i。

输出格式

一行一个非负整数,表示最大的和谐度

样例输入1

3
aaa
bbc
bb
bbb
ac
bbc

样例输出1

6

数据规模和约定

全部数据满足 $\sum_{i=1}^n(\lvert A_i\rvert+\lvert B_i\rvert)\le10^5$。

本版沿用现行 Hydro 评分:所有测试点共 100 分,按上述全局范围评测。