fork(2) download
  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
stdin
Standard input is empty
stdout
Standard output is empty