백준26263 룬 숲

작성일 | In

문제 링크

  • https://icpc.me/26263

사용 알고리즘

  • Suffix Array
  • HLD

풀이

트리에서 두 개의 경로가 주어지면, 두 경로의 최장 공통 접두사의 길이를 구하는 문제입니다.

HLD를 이용하면 경로를 $O(\log N)$개의 부분 문자열로 쪼갤 수 있습니다. 두 경로를 $O(\log N)$개의 부분 문자열로 쪼갠 다음, 앞에 있는 부분 문자열부터 차례대로 접두사가 얼마나 일치하는지 구하면 됩니다.
두 문자열의 최장 공통 접두사를 구하는 것은 LCP 배열에서 RMQ를 하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

pair<vector<int>, vector<int>> SuffixArray(const string &s){
    int n = s.size(), m = max(n, 256);
    vector<int> sa(n), lcp(n), pos(n), tmp(n), cnt(m);
    auto counting_sort = [&](){
        fill(cnt.begin(), cnt.end(), 0);
        for(int i=0; i<n; i++) cnt[pos[i]]++;
        partial_sum(cnt.begin(), cnt.end(), cnt.begin());
        for(int i=0; i<n; i++) sa[--cnt[pos[tmp[i]]]] = tmp[i];
    };
    for(int i=0; i<n; i++) sa[i] = i, pos[i] = s[i], tmp[i] = i;
    counting_sort();
    for(int k=1; ; k<<=1){
        int p = 0;
        for(int i=n-k; i<n; i++) tmp[p++] = i;
        for(int i=0; i<n; i++) if(sa[i] >= k) tmp[p++] = sa[i] - k;
        counting_sort();
        tmp[sa[0]] = 0;
        for(int i=1; i<n; i++){
            tmp[sa[i]] = tmp[sa[i-1]];
            if(sa[i-1]+k < n && sa[i]+k < n && pos[sa[i-1]] == pos[sa[i]] && pos[sa[i-1]+k] == pos[sa[i]+k]) continue;
            tmp[sa[i]] += 1;
        }
        swap(pos, tmp);
        if(pos[sa.back()] + 1 == n) break;
    }
    for(int i=0, j=0; i<n; i++, j=max(j-1,0)){
        if(pos[i] == 0) continue;
        while(sa[pos[i]-1]+j < n && sa[pos[i]]+j < n && s[sa[pos[i]-1]+j] == s[sa[pos[i]]+j]) j++;
        lcp[pos[i]] = j;
    }
    return {sa, lcp};
}

struct RMQ {
    vector<vector<int>> st;
    vector<int> lg;
    RMQ() = default;
    RMQ(const vector<int> &a){
        int n = a.size();
        st = vector<vector<int>>(__lg(n)+1, vector<int>(n));
        for(int i=0; i<n; i++) st[0][i] = a[i];
        for(int i=1; i<st.size(); i++) for(int j=0; j<n; j++) if(j + (1<<i) - 1 < n) st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
        lg.resize(n);
        for(int i=0; i<st.size(); i++) lg[1<<i] = i;
        for(int i=1; i<n; i++) if(!lg[i]) lg[i] = lg[i-1];
    }
    int query(int l, int r){
        if(l > r) return 0x3f3f3f3f;
        int k = lg[r-l+1];
        return min(st[k][l], st[k][r-(1<<k)+1]);
    }
};

int N, Q; char A[202020];
vector<int> Inp[202020], G[202020];
int Dep[202020], Par[202020], Sz[202020], Top[202020], In[202020], Rev[202020];

string S;
vector<int> SA, LCP, Pos;
RMQ ST;

int Query(int a, int b){
    if(a == b) return 0x3f3f3f3f;
    return ST.query(min(Pos[a], Pos[b]) + 1, max(Pos[a], Pos[b]));
}

void DFS1(int v, int b){
    for(auto i : Inp[v]){
        if(i == b) continue;
        Dep[i] = Dep[v] + 1; Par[i] = v;
        DFS1(i, v); G[v].push_back(i);
    }
}

void DFS2(int v){
    Sz[v] = 1;
    for(auto &i : G[v]){
        DFS2(i); Sz[v] += Sz[i];
        if(Sz[i] > Sz[G[v][0]]) swap(G[v][0], i);
    }
}

void DFS3(int v){
    static int pv = 0; In[v] = ++pv; Rev[pv] = v;
    for(auto i : G[v]) Top[i] = i == G[v][0] ? Top[v] : i, DFS3(i);
}

pair<int,int> Block(int s, int e){
    if(In[s] <= In[e]) return { In[s], In[e] - In[s] + 1 };
    else return { N + N - In[e], In[s] - In[e] + 1 };
}
vector<pair<int,int>> GetPath(int u, int v){
    vector<pair<int,int>> l, r;
    while(Top[u] != Top[v]){
        if(Dep[Top[u]] > Dep[Top[v]]) l.push_back(Block(u, Top[u])), u = Par[Top[u]];
        else r.push_back(Block(Top[v], v)), v = Par[Top[v]];
    }
    l.push_back(Block(u, v));
    reverse(r.begin(), r.end());
    for(auto i : r) l.push_back(i);
    return l;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1,s,e; i<N; i++) cin >> s >> e, Inp[s].push_back(e), Inp[e].push_back(s);
    DFS1(1, -1); DFS2(1); DFS3(Top[1]=1);

    for(int i=1; i<=N; i++) S += A[Rev[i]];
    S += "#";
    for(int i=N; i>=1; i--) S += A[Rev[i]];
    tie(SA,LCP) = SuffixArray(S);
    Pos.resize(S.size());
    for(int i=0; i<Pos.size(); i++) Pos[SA[i]] = i;
    ST = RMQ(LCP);

    cin >> Q;
    for(int q=1; q<=Q; q++){
        int s1, e1, s2, e2, res = 0; cin >> s1 >> e1 >> s2 >> e2;
        auto u = GetPath(s1, e1), v = GetPath(s2, e2);
        for(int i=0, j=0, a=0, b=0; i<u.size() && j<v.size(); ){
            int st1 = u[i].first + a, len1 = u[i].second - a;
            int st2 = v[j].first + b, len2 = v[j].second - b;
            int lcp = Query(st1, st2);
            res += min({lcp, len1, len2});
            if(lcp < min(len1, len2)) break;
            if(len1 == min(len1, len2)) i++, a = 0; else a += len2;
            if(len2 == min(len1, len2)) j++, b = 0; else b += len1;
        }
        cout << res << "\n";
    }
}