Cf566a greed + dictionary tree

The main idea of the topic :

Here are two piles of strings , Let you match them in pairs to make $LCP$ And the biggest .

Topic ideas :

The first idea : First insert a bunch of strings into the dictionary tree , Then another pile of strings , One by one greedy query as long as possible LCP, Then delete .

That's not right , Because once you can't match all , Choosing which one to delete will have aftereffect .

Second thought ： On top of that , First put the second pile LCP Delete after sorting .

This is obviously wrong , Delete other strings after LCP It's dynamic . It is also unable to dynamically maintain the string LCP.

Consider that each node in the dictionary tree stores strings containing this prefix . In this way, we can enumeration LCP

If we deal with it layer by layer from leaf nodes , Does it ensure that the processing is in order , From long to short .

let me put it another way : Before processing this node , Let its subtree nodes match first . The remaining unmatched strings can only be found in this LCP Match the .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
struct Node{
    
    int nxt[26];
    vector<int> q[2];
}tr[maxn * 8];
int cnt;
void add (string a , int t , int id){
    
    int n = a.size();
    int u = 0;
    tr[u].q[t].push_back(id);
    for (int i = 0 ; i < n ; i++){
    
        int v = a[i] - 'a';
        if (!tr[u].nxt[v]) tr[u].nxt[v] = ++cnt;
        u = tr[u].nxt[v];
        tr[u].q[t].push_back(id);
    }
}
int match[2][maxn] , ans;
void dfs (int u , int step){
    
    for (int i = 0 ; i < 26 ; i++)
        if (tr[u].nxt[i])
            dfs(tr[u].nxt[i] , step + 1);
    vector<int> t[2];
    for (int i = 0 ; i <= 1 ; i++)
        for (auto & g : tr[u].q[i])
            if (!match[i][g]) t[i].push_back(g);
    int n = min(t[0].size() , t[1].size());
    for (int i = 0 ; i < n ; i++) {
    
        match[0][t[0][i]] = t[1][i];
        match[1][t[1][i]] = t[0][i];
        ans += step;
    }
    return ;
}
int main()
{
    
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1 ; i <= n ; i++){
    
        string a; cin >> a;
        add(a , 0 , i);
    }
    for (int i = 1 ; i <= n ; i++){
    
        string a; cin >> a;
        add(a , 1 , i);
    }
    dfs(0 , 0);
    cout << ans << endl;
    for (int i = 1 ; i <= n ; i++){
    
        cout << i << " " << match[0][i] << endl;
    }
    return 0;
}