Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import core.bitop;
- import core.checkedint;
- import core.simd;
- import core.stdc.stdio;
- import core.stdc.stdlib;
- import core.stdc.string;
- import std.algorithm;
- import std.array;
- import std.ascii;
- import std.bigint;
- import std.bitmanip;
- import std.complex;
- import std.container;
- import std.conv;
- import std.datetime;
- import std.format;
- import std.functional;
- import std.math;
- import std.meta;
- import std.numeric;
- import std.random;
- import std.range;
- import std.regex;
- import std.string;
- import std.typecons;
- import std.variant;
- __gshared:
- bool read(T...)(T ptrs) if (ptrs.length > 0) {
- return readf(' ' ~ replicate("%s ", ptrs.length), ptrs) == ptrs.length;
- }
- T[ ] allocate(T)(size_t n) {
- return (cast(T*)malloc(n * T.sizeof))[0 .. n];
- }
- auto pairwise(R)(R range) if (isForwardRange!R) {
- return lockstep(range, dropOne(range));
- }
- struct Lca(Node, int n, Flag!`checkBackReferences` checkBackReferences = No.checkBackReferences,
- Flag!`assignLineIndices` assignLineIndices = No.assignLineIndices) {
- Node*[n + 1] lp;
- int[n + 1] height;
- static if (assignLineIndices)
- int[n + 1] lineSize;
- void init(Node* root) {
- int gid = 1;
- static if (checkBackReferences)
- alias DfsArgs = AliasSeq!(Node*, const Node*);
- else
- alias DfsArgs = AliasSeq!(Node*);
- int dfs0(DfsArgs args) {
- with (args[0]) {
- id = deepestId = gid++;
- static if (assignLineIndices)
- lineSize[deepestId] = 0;
- int h = bsf(id);
- foreach (node; adj) {
- static if (checkBackReferences) {
- if (node is args[1])
- continue;
- const t = dfs0(node, args[0]);
- } else
- const t = dfs0(node);
- if (t > h) {
- h = t;
- deepestId = node.deepestId;
- }
- lp[node.deepestId] = args[0];
- }
- height[id] = h;
- return h;
- }
- }
- void dfs1(DfsArgs args) {
- with (args[0]) {
- static if (assignLineIndices)
- indexInLine = lineSize[deepestId]++;
- mask |= deepestId & -deepestId;
- foreach (node; adj)
- static if (checkBackReferences) {
- if (node !is args[1]) {
- node.mask = mask;
- dfs1(node, args[0]);
- }
- } else {
- node.mask = mask;
- dfs1(node);
- }
- }
- }
- root.mask = 0x0;
- static if (checkBackReferences) {
- dfs0(root, null);
- dfs1(root, null);
- } else {
- dfs0(root);
- dfs1(root);
- }
- }
- Node* get(Node* x, Node* y) {
- const dpx = x.deepestId, dpy = y.deepestId;
- if (dpx != dpy) {
- const k = bsr(dpx ^ dpy);
- const zh = bsf(x.mask & y.mask & ~0 << height[(dpx >> k | 0x1) << k]);
- Node* raise(int deepestId, int mask) {
- const k = bsr(mask & ((1 << zh) - 1));
- return lp[(deepestId >> k | 0x1) << k];
- }
- if (bsf(x.mask) != zh)
- x = raise(dpx, x.mask);
- if (bsf(y.mask) != zh)
- y = raise(dpy, y.mask);
- }
- return x.id < y.id? x : y;
- }
- }
- struct AutoNode {
- int len;
- AutoNode*[char] next;
- AutoNode* link;
- AutoNode*[ ] invLinks;
- int id, deepestId, mask;
- alias adj = invLinks;
- AutoNode* append(char c, AutoNode* last) {
- auto cur = createNode(AutoNode(last.len + 1));
- AutoNode** p;
- while ((p = c in last.next) is null) {
- last.next[c] = cur;
- last = last.link;
- if (last is null) {
- cur.link = &this;
- return cur;
- }
- }
- auto q = *p;
- if (q.len == last.len + 1) {
- cur.link = q;
- return cur;
- }
- auto clone = createNode(*q);
- clone.len = last.len + 1;
- cur.link = q.link = clone;
- do {
- *p = clone;
- last = last.link;
- if (last is null)
- break;
- p = c in last.next;
- } while (p !is null && *p == q);
- return cur;
- }
- }
- struct TreeNode {
- char c;
- TreeNode*[ ] adj;
- int id, deepestId, mask, indexInLine, indexInString;
- void genString(in TreeNode* prev) {
- indexInString = strSize;
- str[strSize++] = c;
- foreach (node; adj)
- if (node !is prev && node.deepestId == deepestId) {
- node.genString(&this);
- break;
- }
- foreach (node; adj)
- if (node !is prev && node.deepestId != deepestId)
- node.genString(&this);
- }
- }
- struct Waypoint {
- int pos, lpos, trgLpos;
- bool up;
- }
- int n;
- TreeNode[300_000] _nodes;
- int strSize;
- char[300_000] str;
- int auNodesSize;
- AutoNode[ ] auNodes;
- AutoNode*[300_000] _tdNodes, _buNodes;
- AutoNode*[ ] tdNodes, buNodes;
- Lca!(TreeNode, 300_000, Yes.checkBackReferences, Yes.assignLineIndices) treeLca;
- Lca!(AutoNode, 1_200_000) auLca;
- Waypoint[38][2] wp;
- auto createNode()(auto ref AutoNode node) {
- auNodes[auNodesSize] = node;
- return &auNodes[auNodesSize++];
- }
- int solve(TreeNode* a, TreeNode* b, TreeNode* c, TreeNode* d) {
- auto calcWaypoints(const(TreeNode)* a, const(TreeNode)* b, Waypoint[ ] wp) {
- const lca = treeLca.get(a, b);
- int i = 0;
- void walkUp(const(TreeNode)* node, bool up) {
- while (node.deepestId != lca.deepestId) {
- wp[i++] = Waypoint(node.indexInString, node.indexInLine, 0, up);
- node = treeLca.lp[node.deepestId];
- }
- if (up)
- wp[i++] = Waypoint(node.indexInString, node.indexInLine, lca.indexInLine, up);
- }
- walkUp(a, true);
- const mid = i;
- walkUp(b, false);
- wp[mid .. i].reverse();
- return wp[0 .. i];
- }
- auto wp0 = calcWaypoints(a, b, wp[0][ ]);
- auto wp1 = calcWaypoints(c, d, wp[1][ ]);
- int result = 0;
- while (!wp0.empty && !wp1.empty) {
- a = wp0.front;
- c = wp1.front;
- auto node0 = a.up? buNodes[a.pos] : tdNodes[a.pos - a.lpos];
- auto node1 = c.up? buNodes[c.pos] : tdNodes[c.pos - c.lpos];
- const aLim = a.lpos - a.trgLpos + 1;
- const cLim = c.lpos - c.trgLpos + 1;
- const lce = min(auLca.get(node0, node1).len, aLim, cLim);
- }
- /+
- static struct NodeInfo {
- int pos, lpos, dpi;
- }
- bool up1 = c != lca1;
- NodeInfo ai = { a.indexInString, a.indexInLine, a.deepestId };
- NodeInfo ci = { c.indexInString, c.indexInLine, c.deepestId };
- void raise(ref NodeInfo i) {
- auto node = treeLca.lp[i.dpi];
- i.pos = node.indexInString;
- i.lpos = node.indexInLine;
- i.dpi = node.deepestId;
- }
- void shiftUp(ref NodeInfo i, int offset) {
- assert(i.pos >= offset);
- assert(i.lpos >= offset);
- i.pos -= offset;
- i.lpos -= offset;
- }
- while (ai.pos != lca0.indexInString) {
- if (ai.dpi != lca0.deepestId) {
- if (up1) {
- if (ci.dpi != lca1.deepestId) {
- //The simplest case: just go up.
- const aLim = ai.lpos + 1, cLim = ci.lpos + 1;
- const lce = min(auLca.get(buNodes[ai.pos], buNodes[ci.pos]).len, aLim, cLim);
- result += lce;
- if (lce < aLim && lce < cLim)
- return result;
- if (lce == aLim) {
- raise(ai);
- if (lce == cLim)
- raise(ci);
- else
- shiftUp(ci, lce);
- } else {
- raise(ci);
- shiftUp(ai, lce);
- }
- } else {
- //c lays in the same line as lca1.
- const lce = min(
- auLca.get(buNodes[ai.pos], buNodes[ci.pos]).len,
- ai.lpos + 1,
- ci.lpos - lca1.lpos + 1,
- );
- result += lce;
- }
- }
- }
- }
- +/
- return result;
- }
- void main() {
- auNodes = allocate!AutoNode(1_200_000);
- while (scanf("%d ", &n) == 1) {
- auto nodes = _nodes[0 .. n];
- foreach (ref node; nodes)
- node.c = cast(char)getchar();
- foreach (i; 1 .. n) {
- int a, b;
- scanf("%d%d", &a, &b);
- a--;
- b--;
- nodes[a].adj ~= &nodes[b];
- nodes[b].adj ~= &nodes[a];
- }
- treeLca.init(&nodes[0]);
- strSize = 0;
- nodes[0].genString(null);
- assert(strSize == n);
- AutoNode root;
- tdNodes = _tdNodes[0 .. n];
- buNodes = _buNodes[0 .. n];
- auNodesSize = 0;
- //Build automata on reversed strings.
- auto last = &root;
- foreach_reverse (i, c; str[0 .. n])
- last = tdNodes[i] = root.append(c, last);
- foreach (i, c; str[0 .. n])
- last = buNodes[i] = root.append(c, last);
- foreach (ref node; auNodes[0 .. auNodesSize])
- node.link.invLinks ~= &node;
- auLca.init(&root);
- int q;
- scanf("%d", &q);
- while (q--) {
- int a, b, c, d;
- scanf("%d%d%d%d", &a, &b, &c, &d);
- printf("%d\n", solve(&nodes[a - 1], &nodes[b - 1], &nodes[c - 1], &nodes[d - 1]));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement