fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define clr(x) memset((x), 0, sizeof(x))
  4. #define all(x) (x).begin(), (x).end()
  5. #define pb push_back
  6. #define mp make_pair
  7. #define For(i, st, en) for(int i=(st); i<=(int)(en); i++)
  8. #define Ford(i, st, en) for(int i=(st); i>=(int)(en); i--)
  9. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  10. #define ford(i, n) for(int i=(n)-1; i>=0; i--)
  11. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  12. #define in(x) int (x); input((x));
  13. #define x first
  14. #define y second
  15. #define less(a,b) ((a) < (b) - EPS)
  16. #define more(a,b) ((a) > (b) + EPS)
  17. #define eq(a,b) (fabs((a) - (b)) < EPS)
  18. #define remax(a, b) ((a) = (b) > (a) ? (b) : (a))
  19. #define remin(a, b) ((a) = (b) < (a) ? (b) : (a))
  20.  
  21. using namespace std;
  22.  
  23. template <typename T>
  24. T gcd(T a, T b) {
  25.     while (b > 0) {
  26.         a %= b;
  27.         swap(a, b);
  28.     }
  29.     return a;
  30. }
  31.  
  32. typedef long double ld; typedef unsigned int uint; template <class _T> inline _T sqr(const _T& x) {return x * x;} template <class _T> inline string tostr(const _T& a) {ostringstream os(""); os << a; return os.str();} const ld PI = 3.1415926535897932384626433832795L; const double EPS = 1e-9; char TEMPORARY_CHAR;
  33.  
  34. typedef long long ll; typedef unsigned long long ull; typedef set < int > SI; typedef vector < int > VI; typedef vector < vector < int > > VVI; typedef map < string, int > MSI; typedef pair < int, int > PII; const int INF = 1e9; inline void input(int &a) {a = 0; while (((TEMPORARY_CHAR = getchar()) > '9' || TEMPORARY_CHAR < '0') && (TEMPORARY_CHAR != '-')){} char neg = 0; if (TEMPORARY_CHAR == '-') {neg = 1; TEMPORARY_CHAR = getchar();} while (TEMPORARY_CHAR <= '9' && TEMPORARY_CHAR >= '0') {a = 10 * a + TEMPORARY_CHAR - '0'; TEMPORARY_CHAR = getchar();} if (neg) a = -a;} inline void out(long long a) {if (!a) putchar('0'); if (a < 0) {putchar('-'); a = -a;} char s[20]; int i; for(i = 0; a; ++i) {s[i] = '0' + a % 10; a /= 10;} ford(j, i) putchar(s[j]);} inline int nxt() {in(ret); return ret;}
  35.  
  36. const int MAXN = 1000000;
  37. const int LOG = 1000;
  38.  
  39. namespace suf_array {
  40.     static const int MAXLEN = MAXN * 2;
  41.     static const int LOG = 20;
  42.     char s[MAXLEN + 1];
  43.     int n;
  44.     int sa[MAXLEN];
  45.     int lcp[MAXLEN];
  46.     int logTable[MAXLEN];
  47.     int rank[MAXLEN];
  48.     int rmq[LOG + 1][MAXLEN];
  49.     int order[MAXLEN];
  50.     int r[MAXLEN];
  51.     int cnt[MAXLEN];
  52.     int st[MAXLEN];
  53.  
  54.     bool cmp(int i, int j)  {
  55.         return s[i] < s[j];
  56.     }
  57.  
  58.     void process()
  59.     {
  60.         for (int i = 0; i < n; i++)
  61.             order[i] = n - 1 - i;
  62.  
  63.         stable_sort(order, order + n, cmp);
  64.  
  65.         for (int i = 0; i < n; i++) {
  66.             sa[i] = order[i];
  67.             rank[i] = s[i];
  68.         }
  69.  
  70.         for (int len = 1; len < n; len <<= 1) {
  71.             memcpy(r, rank, n * sizeof(int));
  72.             for (int i = 0; i < n; i++) {
  73.                 rank[sa[i]] = (i > 0 && r[sa[i - 1]] == r[sa[i]] &&
  74.                         sa[i - 1] + len < n && r[sa[i - 1] + len / 2] == r[sa[i] + len / 2])
  75.                         ? rank[sa[i - 1]]
  76.                         : i;
  77.             }
  78.             for (int i = 0; i < n; i++)
  79.                 cnt[i] = i;
  80.  
  81.             memcpy(st, sa, sizeof(int) * n);
  82.             for (int i = 0; i < n; i++) {
  83.                 int s1 = st[i] - len;
  84.                 if (s1 >= 0)
  85.                     sa[cnt[rank[s1]]++] = s1;
  86.             }
  87.         }
  88.     }
  89.  
  90.     void calc_lcp() {
  91.         for (int i = 0; i < n; i++)
  92.             rank[sa[i]] = i;
  93.         for (int i = 0, h = 0; i < n; i++) {
  94.             if (rank[i] < n - 1) {
  95.                 int j = sa[rank[i] + 1];
  96.                 while(max(i, j) + h < n && s[i + h] == s[j + h])
  97.                     ++h;
  98.                 lcp[rank[i] + 1] = h;
  99.                 if (h > 0)
  100.                     --h;
  101.             }
  102.         }
  103.  
  104.         logTable[0] = 0;
  105.         logTable[1] = 0;
  106.         for (int i = 2; i < n; i++)
  107.             logTable[i] = logTable[i >> 1] + 1;
  108.  
  109.         for (int i = 0; i < n; ++i)
  110.             rmq[0][i] = lcp[i];
  111.  
  112.         for (int k = 1; (1 << k) < n; ++k) {
  113.             for (int i = 0; i + (1 << k) <= n; i++) {
  114.                 int x = rmq[k - 1][i];
  115.                 int y = rmq[k - 1][i + (1 << k - 1)];
  116.                 rmq[k][i] = min(x, y);
  117.             }
  118.         }
  119.     }
  120.  
  121.     int get_lcp(int l, int r) {
  122.         l = rank[l];
  123.         r = rank[r];
  124.         if (l > r) {
  125.             swap(l, r);
  126.         }
  127.         if (l == r) {
  128.             return n - sa[l];
  129.         }
  130.         ++l;
  131.         int k = logTable[r - l];
  132.         int x = rmq[k][l];
  133.         int y = rmq[k][r - (1 << k) + 1];
  134.         return min(x, y);
  135.     }
  136. };
  137.  
  138.  
  139. namespace hld {
  140.     vector <int> g[MAXN];
  141.     int sz[MAXN];
  142.     int p[MAXN];
  143.  
  144.     int pos_up[MAXN];
  145.     int pos_down[MAXN];
  146.  
  147.     int r[MAXN];
  148.     int root[MAXN];
  149.     int rt[MAXN];
  150.  
  151.     int tin[MAXN];
  152.     int tout[MAXN];
  153.     int timer = 0;
  154.  
  155.     int pos[MAXN];
  156.  
  157.     vector <int> c[MAXN];
  158.  
  159.     int pathCount = 0;
  160.  
  161.     void dfs(int v, int par) {
  162.         p[v] = par;
  163.         sz[v] = 1;
  164.         tin[v] = timer++;
  165.         for (int i = 0; i < (int)g[v].size(); ++i) {
  166.             int to = g[v][i];
  167.             if (to == par) {
  168.                 continue;
  169.             }
  170.             dfs(to, v);
  171.             sz[v] += sz[to];
  172.         }
  173.         tout[v] = timer++;
  174.     }
  175.  
  176.     void decomp(int v, int par, int k) {
  177.         pos[v] = c[k].size();
  178.         c[k].push_back(v);
  179.         root[v] = rt[k];
  180.         r[v] = k;
  181.  
  182.         int x = 0, y = -1;
  183.         for (int i = 0; i < (int)g[v].size(); ++i) {
  184.             int to = g[v][i];
  185.             if (to == par)
  186.                 continue;
  187.             if (sz[to] > x) {
  188.                 x = sz[to];
  189.                 y = to;
  190.             }
  191.         }
  192.         if (y != -1) decomp(y, v, k);
  193.  
  194.         for (int i = 0; i < (int)g[v].size(); ++i) {
  195.             int to = g[v][i];
  196.             if (to != par && to != y) {
  197.                 rt[pathCount] = to;
  198.                 decomp(to, v, pathCount++);
  199.             }
  200.         }
  201.     }
  202.     void initSA(char * s, char * data) {
  203.         int len = 0;
  204.         for (int i = 0; i < pathCount; ++i) {
  205.             for (int j = 0; j < (int)c[i].size(); ++j) {
  206.                 int v = c[i][j];
  207.                 s[pos_down[v] = len++] = data[v];
  208.             }
  209.             for (int j = (int)c[i].size() - 1; j >= 0; --j) {
  210.                 int v = c[i][j];
  211.                 s[pos_up[v] = len++] = data[v];
  212.             }
  213.         }
  214.     }
  215.  
  216.     inline bool upper(int a, int b) {
  217.         return tin[a] <= tin[b] && tout[a] >= tout[b];
  218.     }
  219.     pair <int, int> up[LOG];
  220.     pair <int, int> down[LOG];
  221.  
  222.     int getHeavySegments(int a, int b, pair <int, int> * res) {
  223.         int sup = 0;
  224.         int sdown = 0;
  225.  
  226.         while (!upper(root[a], b)) {
  227.             up[sup++] = make_pair(pos_up[a], pos_up[root[a]]);
  228.             a = p[root[a]];
  229.         }
  230.         while (!upper(root[b], a)) {
  231.             down[sdown++] = make_pair(pos_down[root[b]], pos_down[b]);
  232.             b = p[root[b]];
  233.         }
  234.         assert(r[a] == r[b]);
  235.         if (upper(a, b)) {
  236.             down[sdown++] = make_pair(pos_down[a], pos_down[b]);
  237.         } else {
  238.             up[sup++] = make_pair(pos_up[a], pos_up[b]);
  239.         }
  240.         for (int i = 0; i < sup; ++i) {
  241.             *res++ = up[i];
  242.         }
  243.         for (int i = sdown - 1; i >= 0; --i) {
  244.             *res++ = down[i];
  245.         }
  246.         return sup + sdown;
  247.     }
  248. }
  249.  
  250. int main() {
  251. #ifdef LOCAL
  252.     freopen("input.txt", "r", stdin);
  253. #else
  254.  
  255. #endif
  256.     ios_base::sync_with_stdio(false);
  257.  
  258.     int n;
  259.     scanf("%d", &n);
  260.  
  261.     char data[n + 1];
  262.     scanf("%s", data);
  263.  
  264.     for (int i = 0; i + 1 < n; ++i) {
  265.         int a, b;
  266.         scanf("%d%d", &a, &b);
  267.         --a, --b;
  268.         hld::g[a].push_back(b);
  269.         hld::g[b].push_back(a);
  270.     }
  271.  
  272.     hld::dfs(0, -1);
  273.     hld::decomp(0, -1, hld::pathCount++);
  274.     hld::initSA(suf_array::s, data);
  275.  
  276.     suf_array::n = 2 * n;
  277.     suf_array::process();
  278.     suf_array::calc_lcp();
  279.  
  280.     int m;
  281.     scanf("%d", &m);
  282.  
  283.     pair <int, int> segsL[LOG];
  284.     pair <int, int> segsR[LOG];
  285.  
  286.     while (m--) {
  287.         int a, b, c, d;
  288.         scanf("%d%d%d%d", &a, &b, &c, &d);
  289.         --a, --b, --c, --d;
  290.  
  291.         int lsize = hld::getHeavySegments(a, b, segsL);
  292.  
  293.         int rsize = hld::getHeavySegments(c, d, segsR);
  294.  
  295.         int i = 0, j = 0;
  296.        int len = 0;
  297.        while (i < lsize && j < rsize) {
  298.            int lcp = suf_array::get_lcp(segsL[i].first, segsR[j].first);
  299.            lcp = min(lcp, segsL[i].second - segsL[i].first + 1);
  300.            lcp = min(lcp, segsR[j].second - segsR[j].first + 1);
  301.            len += lcp;
  302.            segsL[i].first += lcp;
  303.            segsR[j].first += lcp;
  304.  
  305.            bool ok = false;
  306.  
  307.            if (segsL[i].first > segsL[i].second) {
  308.                ++i;
  309.                ok = true;
  310.            }
  311.  
  312.            if (segsR[j].first > segsR[j].second) {
  313.                ++j;
  314.                ok = true;
  315.            }
  316.  
  317.            if (!ok) {
  318.                break;
  319.            }
  320.        }
  321.         printf("%d\n", len);
  322.     }
  323.  
  324. #ifdef LOCAL
  325.     cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms.\n";
  326. #endif // LOCAL
  327.     return 0;
  328. }
Success #stdin #stdout 0.02s 294336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/42hc8F
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!