fork 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 = 1000001;
  37. const int LOG = 20;
  38.  
  39. int n;
  40.  
  41. long long mod = 1000000007;
  42. long long p = 31;
  43. long long revP = 129032259;
  44. long long powers[MAXN + 1];
  45. long long rpowers[MAXN + 1];
  46.  
  47.  
  48. void initHashes() {
  49.     powers[0] = rpowers[0] = 1;
  50.     for (int j = 0; j <= n; ++j) {
  51.         powers[j + 1] = powers[j] * p % mod;
  52.         rpowers[j + 1] = rpowers[j] * revP % mod;
  53.     }
  54. }
  55.  
  56. int up[LOG][MAXN];
  57.  
  58. vector <int> g[MAXN];
  59.  
  60. long long UP[MAXN];
  61. long long DOWN[MAXN];
  62.  
  63. char str[MAXN + 1];
  64.  
  65. int tin[MAXN];
  66. int tout[MAXN];
  67. int h[MAXN];
  68.  
  69. int timer = 0;
  70.  
  71. void dfs(int v, int par) {
  72.     tin[v] = timer++;
  73.     up[0][v] = par;
  74.     for (int i = 1; i < LOG; ++i) {
  75.         up[i][v] = up[i - 1][up[i - 1][v]];
  76.     }
  77.     for (int i = 0; i < (int)g[v].size(); ++i) {
  78.         int to = g[v][i];
  79.         if (to == par) continue;
  80.         h[to] = h[v] + 1;
  81.         UP[to] = (UP[v] + (str[to] - 'a' + 1) * powers[h[to] - 1]) % mod;
  82.         DOWN[to] = (DOWN[v] * p + str[to] - 'a' + 1) % mod;
  83.  
  84.         dfs(to, v);
  85.     }
  86.     tout[v] = timer++;
  87. }
  88.  
  89. inline long long getUp(int v1, int v2) {
  90.     long long res;
  91.     res = (UP[v1] - UP[up[0][v2]] + mod) * rpowers[h[v2] - 1];
  92.  
  93.     if (res >= mod) {
  94.         res %= mod;
  95.     }
  96.  
  97.     return res;
  98. }
  99.  
  100. inline long long getDown(int v1, int v2) {
  101.     long long res = DOWN[v2] - DOWN[v1] * powers[h[v2] - h[v1]] % mod + mod;
  102.  
  103.     if (res >= mod) {
  104.         res -= mod;
  105.     }
  106.     return res;
  107. }
  108.  
  109. bool upper(int a, int b) {
  110.     return tin[a] <= tin[b] && tout[a] >= tout[b];
  111. }
  112.  
  113. int lca(int a, int b) {
  114.     if (upper(a, b)) {
  115.         return a;
  116.     }
  117.     if (upper(b, a)) {
  118.         return b;
  119.     }
  120.     for (int i = LOG - 1; i >= 0; --i) {
  121.         if (!upper(up[i][a], b)) {
  122.             a = up[i][a];
  123.         }
  124.     }
  125.     return up[0][a];
  126. }
  127.  
  128. int get(int v, int k) {
  129.     for (int i = 0; i < LOG; ++i) {
  130.         if (k & (1 << i)) {
  131.             v = up[i][v];
  132.         }
  133.     }
  134.     return v;
  135. }
  136.  
  137. long long getHash(int a, int b, int l, int cnt) {
  138.     int len = h[a] + h[b] - 2 * h[l] + 1;
  139.     if (cnt > h[a] - h[l] + 1) {
  140.         long long h1 = getUp(a, l);
  141.         int v = get(b, len - cnt);
  142.         long long h2 = getDown(l, v);
  143.         h2 -= (str[l] - 'a' + 1) * powers[h[v] - h[l]] % mod;
  144.         if (h2 < 0) {
  145.             h2 += mod;
  146.         }
  147.         return (h1 * powers[h[v] - h[l]] + h2) % mod;
  148.     } else {
  149.         int v = get(a, cnt - 1);
  150.         return getUp(a, v);
  151.     }
  152. }
  153.  
  154. const int M = 1000000;
  155.  
  156. int a[M][2], b[M][2], lc[M][2], res[M * 2], needH[M * 2], l[M], r[M], len[M][2];
  157.  
  158. long long hashToLca[M][2];
  159.  
  160. int * queries[MAXN];
  161.  
  162. int sz[MAXN];
  163.  
  164. int cnt[MAXN];
  165.  
  166. int pos = 0;
  167.  
  168. int st[MAXN];
  169. int ptr[MAXN];
  170. char used[MAXN];
  171.  
  172. inline void dfsQ(int v, int par) {
  173.     st[pos] = v;
  174.     ptr[pos] = 0;
  175.     ++pos;
  176.  
  177.     while (pos) {
  178.         v = st[pos - 1];
  179.         int & i = ptr[pos - 1];
  180.  
  181.         if (i == 0) {
  182.             used[v] = 1;
  183.             for (int j = 0; j < sz[v]; ++j) {
  184.                 int q = queries[v][j];
  185.                 res[q] = st[pos - needH[q] - 1];
  186.             }
  187.             sz[v] = 0;
  188.         }
  189.  
  190.         if (i < (int)g[v].size()) {
  191.             int to = g[v][i++];
  192.             if (!used[to]) {
  193.                 st[pos] = to;
  194.                 ptr[pos] = 0;
  195.                 ++pos;
  196.             }
  197.         } else {
  198.             used[v] = 0;
  199.             --pos;
  200.         }
  201.     }
  202. }
  203.  
  204. int main() {
  205. #ifdef LOCAL
  206.     freopen("input.txt", "r", stdin);
  207. #else
  208.  
  209. #endif
  210.     ios_base::sync_with_stdio(false);
  211.  
  212.     scanf("%d", &n);
  213.     initHashes();
  214.  
  215.     scanf("%s", str);
  216.  
  217.     for (int i = 0; i + 1 < n; ++i) {
  218.         int s, t;
  219.         scanf("%d%d", &s, &t);
  220.         --s, --t;
  221.         g[s].push_back(t);
  222.         g[t].push_back(s);
  223.     }
  224.  
  225.     g[n].push_back(0);
  226.  
  227.     dfs(n, n);
  228.  
  229.     int q;
  230.     scanf("%d", &q);
  231.  
  232.     //cerr << getlong long(0, 2, 0, 3).h[0] << endl;
  233.  
  234.     //cerr << 31 * 31 * 1 + 31 * 2 + 2 << endl;
  235.  
  236.     for (int i = 0; i < q; ++i) {
  237.         for (int j = 0; j < 2; ++j) {
  238.             scanf("%d%d", &a[i][j], &b[i][j]);
  239.             --a[i][j], --b[i][j];
  240.             int A = a[i][j];
  241.             int B = b[i][j];
  242.             cnt[A]++;
  243.             cnt[B]++;
  244.             int C = lc[i][j] = lca(A, B);
  245.             len[i][j] = h[A] + h[B] - 2 * h[C] + 1;
  246.             hashToLca[i][j] = getUp(A, C) - DOWN[C];
  247.             if (hashToLca[i][j] < 0) {
  248.                 hashToLca[i][j] += mod;
  249.             }
  250.         }
  251.         l[i] = 0;
  252.         r[i] = min(len[i][0], len[i][1]);
  253.     }
  254.  
  255.     for (int i = 0; i < n; ++i) {
  256.         queries[i] = new int[cnt[i]];
  257.     }
  258.  
  259.     while (true) {
  260.         bool ok = true;
  261.         for (int i = 0; i < q; ++i) {
  262.             if (l[i] == r[i]) {
  263.                 continue;
  264.             }
  265.             ok = false;
  266.             int m = (l[i] + r[i] + 1) >> 1;
  267.             for (int j = 0; j < 2; ++j) {
  268.                 if (m > h[a[i][j]] - h[lc[i][j]]) {
  269.                     needH[i * 2 + j] = len[i][j] - m;
  270.                     queries[b[i][j]][sz[b[i][j]]++] = i * 2 + j;
  271.                 } else {
  272.                     needH[i * 2 + j] = m;
  273.                     queries[a[i][j]][sz[a[i][j]]++] = i * 2 + j;
  274.                 }
  275.             }
  276.         }
  277.         if (ok) {
  278.             break;
  279.         }
  280.  
  281.         dfsQ(0, 0);
  282.  
  283.         for (int i = 0; i < q; ++i) {
  284.             if (l[i] == r[i]) {
  285.                 continue;
  286.             }
  287.             int m = (l[i] + r[i] + 1) >> 1;
  288.             long long ha[2];
  289.             for (int j = 0; j < 2; ++j) {
  290.                 if (m > h[a[i][j]] - h[lc[i][j]]) {
  291.                     int v = res[i * 2 + j];
  292.                     ha[j] = hashToLca[i][j] * powers[h[v] - h[lc[i][j]]] + DOWN[v];
  293.                 } else {
  294.                     int v = res[i * 2 + j];
  295.                     ha[j] = (UP[a[i][j]] - UP[v] + mod) * rpowers[h[v]];
  296.                 }
  297.             }
  298.             if ((ha[0] - ha[1]) % mod == 0) {
  299.                 l[i] = m;
  300.             } else {
  301.                 r[i] = m - 1;
  302.             }
  303.         }
  304.     }
  305.  
  306.     for (int i = 0; i < q; ++i) {
  307.         printf("%d\n", l[i]);
  308.     }
  309.  
  310. #ifdef LOCAL
  311.     cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms.\n";
  312. #endif // LOCAL
  313.     return 0;
  314. }
Runtime error #stdin #stdout 4.14s 227904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2OxibB
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!