LCP on a Tree

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]));
        }
    }
}