为什么用树链剖分就会t啊。。。（代码已经是从隔壁模板粘过来的了。。。）

#include<bits/stdc++.h>
using namespace std;
const int mn = 1000005;
char s[mn];
int nxt[mn];
int to[mn], nxtt[mn], head[mn], cnt;
int dep[mn], fa[mn], siz[mn], son[mn], top[mn];
int f[mn][21];
inline int getint()
{
    int x = 0; char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    while(c >= '0' && c <= '9')
        x *= 10, x += c - '0', c = getchar();
    return x;
}
inline void addedge(int a, int b)
{
    to[++cnt] = b, nxtt[cnt] = head[a], head[a] = cnt;
}
void dfs1(int s, int f, int d)
{
    fa[s] = f, dep[s] = d, siz[s] = 1;
    for(int i = head[s]; i; i = nxtt[i])
    {
        int t = to[i];
        if(t != f)
        {
            dfs1(t, s, d + 1), siz[s] += siz[t];
            if(siz[son[s]] < siz[t])
                son[s] = t;
        }
    }
}
void dfs2(int s)
{
    if(son[s])
        top[son[s]] = top[s], dfs2(son[s]);
    for(int i = head[s]; i; i = nxtt[i])
    {
        int t = to[i];
        if(t != fa[s] && t != son[s])
            top[t] = t, dfs2(t);
    }
}
inline int lca(int a, int b)
{
    while(top[a] != top[b])
        if(dep[top[a]] > dep[top[b]])   a = fa[top[a]];
        else                            b = fa[top[b]];
    return dep[a] < dep[b] ? a : b;
}
int main()
{
    int n, m, a, b;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    nxt[0] = -1;
    for(int i = 1; i <= n; i++)
    {
        int j = nxt[i - 1];
        while(j != -1 && s[j + 1] != s[i])
            j = nxt[j];
        nxt[i] = j + 1, addedge(nxt[i], i);
    }
    dfs1(0, 0, 0), dfs2(0);
    m = getint();
    while(m--)
    {
        a = getint(), b = getint();
        int ans = lca(a, b);
        if(a > b) swap(a, b);
        if(ans == a) ans = nxt[ans];
        printf("%d\n", ans);
    }
}