[CF566A]Matching Names

题目大意：

A组和B组各\(n(n\le10^5)\)个字符串\((\sum|S|\le8\times10^5)\)，将它们两两匹配，使得每组两个字符串的LCP之和最大，输出最大值，并输出方案。

思路：

Trie上贪心，在深的结点能匹配则匹配。

源代码：

#include
    
     #include
     
      #include
      
       const int N=1e5+1,L=8e5+1;int n,ans;char s[L];std::vector
       
        
          > v;class Trie {    private:        std::set
         
           set[L][2]; int ch[L][26],par[L],sz; int idx(const char &c) const { return c-'a'; } void erase(int p,const int &x,const bool &t) { while(p) { set[p][t].erase(x); p=par[p]; } set[0][t].erase(x); } public: void insert(char s[],const int &id,const bool &t) { set[0][t].insert(id); for(register int i=0,p=0;s[i];i++) { const int c=idx(s[i]); if(!ch[p][c]) { ch[p][c]=++sz; par[ch[p][c]]=p; } p=ch[p][c]; set[p][t].insert(id); } } void solve(const int &p,const int &dep) { for(register int i=0;i<26;i++) { if(ch[p][i]) { solve(ch[p][i],dep+1); } } while(!set[p][0].empty()&&!set[p][1].empty()) { ans+=dep; const int x=*set[p][0].begin(); const int y=*set[p][1].begin(); v.push_back(std::make_pair(x,y)); erase(p,x,0); erase(p,y,1); } }};Trie t;int main() { scanf("%d",&n); for(register int i=1;i<=n;i++) { scanf("%s",s); t.insert(s,i,0); } for(register int i=1;i<=n;i++) { scanf("%s",s); t.insert(s,i,1); } t.solve(0,0); printf("%d\n",ans); for(register unsigned i=0;i