题意
有 \(n\) 名同学，每位同学有一个真名与一个笔名，都是一个由小写英文字母组成的字符串。每位同学可以选择一位同学，使自己的真名与那位同学的笔名相匹配，产生的贡献为其最长公共前缀，每位同学的笔名只能与一人匹配，求贡献总和的最大值。
思路
把笔名插入字典树，并在每个结束点 \(i\) 打上标记，标记位置 \(i\) 到根组成的字符串是某个同学的笔名。
然后枚举每个人的真名，找字典树中所有笔名中的最长公共前缀，在最长前缀的末尾 \(i\) 打上标记，标记位置 \(i\) 到根组成的字符串是某个同学的真名与所有笔名的最长公共前缀。
最后遍历一遍字典树，进行后序遍历，若搜索至位置 \(i\)，若位置 \(i\) 上有同学的笔名标记，加入栈中。若位置 \(i\) 上有同学的真名标记，如果栈非空，就用栈内的记录的同学与之配对，其公共前缀的长度为当前节点的深度。反之，将标记上放到其父节点中，即缩小某同学的真名与所有笔名的最长公共前缀长度。
但存在一定的问题，如果已经搜索了子树 \(x\)，进行操作后栈不为空，随后又搜索了子树 \(y\)，且 \(y\) 的深度不低于 \(x\)。若子树 \(y\) 中存在同学的真名标记，就会与栈内的元素配对，而这样计算的答案就是错误的，实际匹配的贡献值应当更小。因此，在进行更深的搜索时应清空栈，但回溯后又需要还原栈的历史状态，很简单，记录搜索到当前节点时的栈大小，让搜索完当前子树后的栈大小与之作差就可以得到实际的栈大小，同时保留剩余的栈元素。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 8e5 + 5 , M = 2e5 + 5;
int n;
string s[M];
int trie[N][27] , tot , ans[M] , sta[M] , top , h = 0;
vector<int>w[N] , vis[N];
void insert(string x , int val) {int i = 0;for(auto v : x) {int k = v - 'a';if(!trie[i][k]) trie[i][k] = ++ tot;i = trie[i][k];}vis[i].push_back(val); // 标记位置 $i$ 到根组成的字符串是某个同学的笔名。
}
void find(string x , int val) {int i = 0;for(auto v : x) {int k = v - 'a';if(!trie[i][k]) break;i = trie[i][k];}w[i].push_back(val); // 标记位置 $i$ 到根组成的字符串是某个同学的真名与所有笔名的最长公共前缀。
}
void dfs(int i , int fa , int dep , int tp) {for(auto v : vis[i]) {sta[++ top] = v; // 把当前位置的笔名标记加入栈中}for(int v = 0 ; v < 26 ; v ++) {if(!trie[i][v]) continue;dfs(trie[i][v] , i , dep + 1 , top);}for(int j = w[i].size() - 1 ; j >= 0 ; j --) {int v = w[i][j];if(top - tp > 0) { // 若栈不为空ans[v] = sta[top --]; // 匹配h += dep; // 计算答案} else { // 若栈为空w[fa].push_back(v); // 上放到其父节点中}w[i].pop_back();}
}
int main() {cin>>n;for(int i = 1 ; i <= n + n ; i ++) cin>>s[i];for(int i = n + 1 ; i <= n + n ; i ++) insert(s[i] , i - n); // 把笔名插入字典树for(int i = 1 ; i <= n ; i ++) find(s[i] , i); // 找每个真名与所有笔名中的最长公共前缀 dfs(0 , 0 , 0 , 0);cout<<h<<'\n';for(int i = 1 ; i <= n ; i ++) {cout<<i<<' '<<ans[i]<<'\n';}return 0;
}