내가 만든 알고리즘 라이브러리

 

//Trie

struct trie {
    struct node {
        bool terminal;
        map<char, node*> child;
        node() : terminal(false) {}
    };

    node* head = new node();

    void store(string str) {
        store_dfs(str, 0, head);
    }

    bool find(string str) {
        return find_dfs(str, 0, head);
    }

private:
    void store_dfs(string str, int n, node* now) {
        if(n == str.size()) {
            now->terminal = true;
            return;
        }

        if(now->child.find(str[n]) == now->child.end()) 
            now->child[str[n]] = new node();

        store_dfs(str, n + 1, now->child[str[n]]);
        now->terminal = false;
    }

    bool find_dfs(string str, int n, node* now) {
        if(str.size() == n) return true;
        if(now->terminal) return false;

        bool ret = false;
        for(auto nxt : now->child) {
            if(str[n] == nxt.first)
                ret |= find_dfs(str, n + 1, nxt.second);
        }

        return ret;
    }
};




//Aho-Corasic
struct Aho_Corasic {

    struct node {
        char now_char;
        map<char, node*> child;
        node* fail;
        bool terminal;

        node(char c) {
            now_char = c;
            terminal = false;
        }
        
        ~node() {
        	for(auto it = child.begin(); it != child.end(); it++) delete it->second;
        }
    };

    node* root;
    
    Aho_Corasic() {
        root = new node(' ');
        root->fail = root;
    }

    ~Aho_Corasic() {
        delete root;
    }

    void insert(string str) {
        node* now = root;
        for(char c : str) {
            if(now->child.find(c) == now->child.end()) now->child[c] = new node(c);
            now = now->child[c];
        }
        now->terminal = true;
    }

    void failure() {
        queue<node*> q;
        root->fail = root;
        q.push(root);

        while(!q.empty()) {
            node* now = q.front(); q.pop();
            for(auto it = now->child.begin(); it != now->child.end(); it++) {
                node* next = it->second;
                char next_char = next->now_char;
                if(now == root) {
                    next->fail = root;
                }
                else {
                    node* failnode = now->fail;

                    while(failnode != root && failnode->child.find(next_char) == failnode->child.end()) {
                        failnode = failnode->fail;
                    }
                    if(failnode->child.find(next_char) != failnode->child.end()) {
                        failnode = failnode->child[next_char];
                    }

                    next->fail = failnode;
                }
                if(next->fail->terminal) next->terminal = true;
                q.push(next);
            }
        }
    }

    bool query(string str) {
        node* now = root;

        for(char c : str) {
            while(now != root && now->child.find(c) == now->child.end())
                now = now->fail;
            if(now->child.find(c) != now->child.end()) now = now->child[c];
            if(now->terminal) return true;
        }

        return false;
    }
};



//최소 공통 조상(LCA);
const int MN = 100001;
vector<int> g[MN];

int h[MN];
int dp[20][MN];

void dfs(int n, int prev) {
    for(int nxt : g[n]) {
        if(nxt == prev) continue;
        h[nxt] = h[n] + 1;
        dp[0][nxt] = n;
        dfs(nxt, n);
    }
}

int LCA(int a, int b) {
    if(h[a] < h[b]) swap(a, b);

    int gap = h[a] - h[b];

    for(int i = 0; i < 20; i++)
        if(gap & (1 << i))
            a = dp[i][a];

    if(a == b) return a;

    for(int i = 19; i >= 0; i--)
        if(dp[i][a] != dp[i][b])
            a = dp[i][a], b = dp[i][b];

    return dp[0][a];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);

    int N; cin >> N;
    for(int i = 0; i < N-1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

    for(int i = 1; i < 20; i++)
        for(int j = 1; j <= N; j++)
            dp[i][j] = dp[i-1][dp[i-1][j]];

    int M; cin >> M;
    while(M--) {
        int a, b; cin >> a >> b;
        cout << LCA(a, b) << '\n';
    }
}