문제 개요

문자열과 연관된 값들의 집합이 주어졌을 때, Trie 자료구조를 활용하여 유효한 구조인지 판별하고 최소 노드 개수를 구하는 문제입니다.

무효 조건 분석

다음 상황에서는 유효한 Trie 구조를 구성할 수 없습니다:

• 동일한 문자열이 서로 다른 값을 가지는 경우
• 여러 값들이 동일한 LCA 노드를 공유하는 경우
• 루트에서 LCA 노드까지의 경로에 제한된 노드가 존재하는 경우

해결 전략

동일한 값을 가진 문자열 그룹은 반드시 해당 그룹의 LCA 노드에서 분기해야 합니다. LCA 노드 이후의 자식 노드들은 다른 값의 LCA를 포함할 수 없도록 제한됩니다.

예시:

3
ab 1
ac 1
ad 2

이 경우 노드 2에서 'b'와 'c' 방향으로 향하는 자식 노드들은 더 이상의 하위 트리를 가질 수 없습니다.

구현 세부사항

유효성 검증 후 최소 노드 수를 계산할 때, LCA가 아닌 노드에서 자식 노드의 LCA 개수가 1인 경우 해당 자식 노드를 부모 노드로 병합할 수 있습니다.

코드 구현

#include <bits/stdc++.h>
using namespace std;

const int MAX_NODES = 100005;
const int MAX_LOG = 22;

struct ValueMapper {
    int values[MAX_NODES], count, size;
    
    void add(int x) { values[count++] = x; }
    
    void prepare() {
        sort(values, values + count);
        size = unique(values, values + count) - values;
    }
    
    int getId(int x) {
        return lower_bound(values, values + size, x) - values + 1;
    }
};

class TrieStructure {
private:
    int nodes[MAX_NODES][26], nodeCount;
    int depth[MAX_NODES], parent[MAX_NODES][MAX_LOG], logTable[MAX_NODES];
    int lcaMark[MAX_NODES], restricted[MAX_NODES];
    int lcaCount[MAX_NODES], active[MAX_NODES];

public:
    void initialize() {
        nodeCount = 1;
        memset(nodes[1], 0, sizeof(nodes[1]));
    }
    
    int addString(const string &s) {
        int current = 1;
        for (char c : s) {
            int idx = c - 'a';
            if (!nodes[current][idx]) {
                nodes[current][idx] = ++nodeCount;
                memset(nodes[nodeCount], 0, sizeof(nodes[nodeCount]));
            }
            current = nodes[current][idx];
        }
        return current;
    }
    
    void setupLog(int n) {
        for (int i = 1; i <= n; i++) {
            logTable[i] = logTable[i-1] + ((1 << logTable[i-1]) == i);
        }
    }
    
    void buildTree(int u, int p) {
        parent[u][0] = p;
        depth[u] = depth[p] + 1;
        
        for (int i = 1; i <= logTable[depth[u]]; i++)
            parent[u][i] = parent[parent[u][i-1]][i-1];
            
        for (int i = 0; i < 26; i++) {
            int v = nodes[u][i];
            if (v && v != p) buildTree(v, u);
        }
    }
    
    void prepareLCA() {
        buildTree(1, 1);
    }
    
    int findLCA(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        
        while (depth[u] > depth[v])
            u = parent[u][logTable[depth[u]-depth[v]]-1];
            
        if (u == v) return u;
        
        for (int k = logTable[depth[u]]-1; k >= 0; k--) {
            if (parent[u][k] != parent[v][k]) {
                u = parent[u][k];
                v = parent[v][k];
            }
        }
        return parent[u][0];
    }
    
    void resetMarks() {
        for (int i = 1; i <= nodeCount; i++) {
            lcaMark[i] = restricted[i] = 0;
        }
    }
    
    bool validateRestrictions(int u, bool restrictionFlag) {
        if (restricted[u]) restrictionFlag = true;
        if (lcaMark[u] && restrictionFlag) return false;
        
        for (int i = 0; i < 26; i++) {
            int v = nodes[u][i];
            if (v && !validateRestrictions(v, restrictionFlag))
                return false;
        }
        return true;
    }
    
    void computeAnswer(int u) {
        int mergeCandidate = 0;
        for (int i = 0; i < 26; i++) {
            int v = nodes[u][i];
            if (v) {
                computeAnswer(v);
                lcaCount[u] += lcaCount[v];
                if (lcaCount[v] == 1) mergeCandidate = v;
            }
        }
        if (lcaMark[u]) lcaCount[u]++;
        
        if (!lcaMark[u] && mergeCandidate) {
            active[u] = 1;
            active[mergeCandidate] = 0;
        } else if (lcaCount[u]) {
            active[u] = 1;
        }
    }
    
    int getMinNodes() {
        for (int i = 1; i <= nodeCount; i++) {
            lcaCount[i] = active[i] = 0;
        }
        computeAnswer(1);
        
        int total = 0;
        for (int i = 1; i <= nodeCount; i++) total += active[i];
        return total;
    }
    
    int* getLCAMark() { return lcaMark; }
    int* getRestricted() { return restricted; }
    int** getNodes() { return nodes; }
    int* getDepth() { return depth; }
};

TrieStructure trie;
string inputs[MAX_NODES];
int values[MAX_NODES], endPoints[MAX_NODES];
vector<int> valueGroups[MAX_NODES];

int main() {
    trie.setupLog(MAX_NODES - 1);
    int testCases;
    cin >> testCases;
    
    for (int caseNum = 1; caseNum <= testCases; caseNum++) {
        ValueMapper mapper;
        mapper.count = 0;
        
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> inputs[i] >> values[i];
            mapper.add(values[i]);
        }
        mapper.prepare();
        
        for (int i = 1; i <= n; i++)
            values[i] = mapper.getId(values[i]);
        
        unordered_map<int, int> endpointValues;
        bool valid = true;
        
        trie.initialize();
        for (int i = 1; i <= n; i++) {
            endPoints[i] = trie.addString(inputs[i]);
            if (endpointValues.count(endPoints[i])) {
                if (endpointValues[endPoints[i]] != values[i]) {
                    valid = false;
                    break;
                }
            }
            endpointValues[endPoints[i]] = values[i];
        }
        
        if (!valid) {
            cout << "Case #" << caseNum << ": -1" << endl;
            continue;
        }
        
        trie.prepareLCA();
        
        for (int i = 1; i <= mapper.size; i++)
            valueGroups[i].clear();
            
        for (int i = 1; i <= n; i++)
            valueGroups[values[i]].push_back(i);
        
        trie.resetMarks();
        for (int i = 1; i <= mapper.size && valid; i++) {
            int groupLCA = endPoints[valueGroups[i][0]];
            for (int j = 1; j < valueGroups[i].size(); j++)
                groupLCA = trie.findLCA(groupLCA, endPoints[valueGroups[i][j]]);
            
            if (trie.getLCAMark()[groupLCA]) {
                valid = false;
                break;
            }
            
            trie.getLCAMark()[groupLCA] = i;
            int lcaDepth = trie.getDepth()[groupLCA];
            
            for (int idx : valueGroups[i]) {
                if (inputs[idx].length() >= lcaDepth) {
                    char nextChar = inputs[idx][lcaDepth - 1];
                    int childNode = trie.getNodes()[groupLCA][nextChar - 'a'];
                    trie.getRestricted()[childNode] = 1;
                }
            }
        }
        
        if (!valid || !trie.validateRestrictions(1, false)) {
            cout << "Case #" << caseNum << ": -1" << endl;
            continue;
        }
        
        cout << "Case #" << caseNum << ": " << trie.getMinNodes() << endl;
    }
    
    return 0;
}