CF504E Misha and LCP on Tree

#include <cstdio> 
#include <cstring> 
#include <vector>  
#include <queue>    
#include <algorithm>  
#include <stack> 
#define setIO(s) freopen(s".in","r",stdin)        
using namespace std;   

namespace sam
{   
    #define N 1200004   
    int last,tot; 
    int ch[N][27],pre[N],mx[N];  
    inline int extend(int c)        
    { 
        if(ch[last][c])     
        {     
            int p=last; 
            int q=ch[p][c];     
            if(mx[q]==mx[p]+1) last=q;   
            else 
            {
                int nq=++tot;               
                mx[nq]=mx[p]+1;   
                memcpy(ch[nq],ch[q],sizeof(ch[q]));   
                pre[nq]=pre[q],pre[q]=nq;   
                for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;    
                last=nq;     
            }    
        }
        else
        {
            int np=++tot,p=last;   
            mx[np]=mx[p]+1,last=np; 
            for(;p&&!ch[p][c];p=pre[p]) ch[p][c]=np;   
            if(!p) pre[np]=1;   
            else
            {
                int q=ch[p][c]; 
                if(mx[q]==mx[p]+1) pre[np]=q;  
                else 
                {
                    int nq=++tot;    
                    mx[nq]=mx[p]+1; 
                    memcpy(ch[nq],ch[q],sizeof(ch[q]));    
                    pre[nq]=pre[q],pre[np]=pre[q]=nq;   
                    for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;      
                }
            }
            last=np;    
        }
        return last;    
    }
    #undef N 
}; 

// 优美的后缀自动机   

namespace suffix_tree
{   
    #define LOG 21       
    #define N 1200006    
    vector<int>G[N];   
    int fa[LOG][N],dis[N];                  
    void dfs(int u,int ff) 
    { 
        int i,j;         
        dis[u]=dis[ff]+1;                       
        fa[0][u]=sam::pre[u];     
        for(i=1;i<LOG;++i) fa[i][u]=fa[i-1][fa[i-1][u]];   
        for(i=0;i<(int)G[u].size();++i) dfs(G[u][i],u);           
    }   
    inline void build() 
    {
        int i,j; 
        for(i=2;i<=sam::tot;++i) 
        {
            G[sam::pre[i]].push_back(i);        
        }
        dfs(1,0);    
    } 
    inline int jump(int x,int len) 
    {
        for(int i=LOG-1;i>=0;--i) if(sam::mx[fa[i][x]]>=len) x=fa[i][x];    
        return x;   
    }
    inline int LCA(int x,int y) 
    { 
        if(dis[x]!=dis[y]) 
        {
            if(dis[x]>dis[y]) swap(x,y);     
            for(int i=LOG-1;i>=0;--i) if(dis[fa[i][y]]>=dis[x]) y=fa[i][y];    
        } 
        if(x==y) return x;   
        for(int i=LOG-1;i>=0;--i)  if(fa[i][x]!=fa[i][y]) x=fa[i][x], y=fa[i][y];     
        return fa[0][x];        
    }      
    #undef N 
    #undef LOG 
};        

// 优美的后缀树 

namespace tree 
{  
    #define N 300003   
    int tot;     
    int son[N],size[N],dep[N],dfn[N],top[N],fa[N],up[N],down[N],val[N];        
    vector<int>G[N];       
    struct node 
    {
        int u,c;   
        node(int u=0,int c=0):u(u),c(c){}  
    };   
    vector<node>A[N];    
    inline void add(int u,int v) 
    {
        G[u].push_back(v); 
        G[v].push_back(u);   
    }   
    void dfs1(int u,int ff) 
    { 
        fa[u]=ff,dep[u]=dep[ff]+1,size[u]=1; 
        for(int i=0;i<G[u].size();++i) 
        {
            if(G[u][i]==ff) continue;   
            dfs1(G[u][i],u);  
            size[u]+=size[G[u][i]];   
            if(size[G[u][i]]>size[son[u]]) son[u]=G[u][i];       
        }
    } 
    void dfs2(int u,int tp) 
    { 
        top[u]=tp;  
        if(tp==u) dfn[tp]=++tot;                
        A[dfn[tp]].push_back(node(u, val[u]));    
        if(son[u]) dfs2(son[u],tp); 
        for(int i=0;i<G[u].size();++i) 
            if(G[u][i]!=son[u]&&G[u][i]!=fa[u]) 
                dfs2(G[u][i], G[u][i]);                               
    }      
    inline void build() 
    {      
        int i,j;   
        dfs1(1,0);  
        dfs2(1,1);  
        for(i=1;i<=tot;++i)      
        {   
            sam::last=1;    
            // 从上到下 （实际是从下到上）         
            for(j=0;j<A[i].size();++j) 
            {     
                int u=A[i][j].u;   
                int c=A[i][j].c;     
                up[u]=sam::extend(c);     
            }
            // 从下到上 （实际上是从上到下） 
            sam::last=1;   
            for(j=A[i].size()-1;j;--j) 
            {
                int u=A[i][j].u; 
                int c=A[i][j].c;  
                down[u]=sam::extend(c);   
            }
        }
    } 
    int LCA(int x,int y) 
    {
        while(dep[x]!=dep[y]) dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];    
        return dep[x]<dep[y]?x:y;   
    }
    #undef N 
};  
 
// 优美的树链剖分   
 
struct node 
{   
    int u,len; 
    node(int u=0,int len=0):u(u),len(len){}   
};  
#define N 300003    
char S[N];  
vector<node>A[2];     
stack<node>ss;  
void insert(int a,int b,int id) 
{
    int lca=tree::LCA(a,b);       
    // 向上走    
    while(tree::dep[a]>tree::dep[lca]) 
    {
        A[id].push_back(node(tree::up[a], min(tree::dep[lca],tree::dep[tree::top[a]])-tree::dep[a]+1));    
        a=tree::fa[tree::top[a]];         
    }
    // 向下走   
    if(a==lca) 
    {   
        while(tree::dep[b]>=tree::dep[lca]) 
        {
            ss.push(node(tree::down[b], min(tree::dep[lca],tree::dep[tree::top[b]])-tree::dep[b]+1));   
            b=tree::fa[tree::top[b]];   
        }
    } 
    else 
    {
        while(tree::dep[b]>tree::dep[lca]) 
        {
            ss.push(node(tree::down[b], min(tree::dep[lca],tree::dep[tree::top[b]])-tree::dep[b]+1));   
            b=tree::fa[tree::top[b]];   
        }
    }
    while(!ss.empty()) A[id].push_back(ss.top()),ss.pop();    
}            
int main() 
{ 
    setIO("input");     
    int i,j,n,m;        
    scanf("%d%s",&n,S+1);      
    for(i=1;i<=n;++i) tree::val[i]=S[i]-‘a‘;        
    for(i=1;i<=n;++i)  
    {
        int u,v; 
        scanf("%d%d",&u,&v); 
        tree::add(u,v);   
    }
    sam::tot=1;     
    tree::build();              // 建完树剖  +  上/下走定位到后缀自动机的位置   
    suffix_tree::build();       // 建完后缀树    
// =========================================================================   
    scanf("%d",&m); 
    for(i=1;i<=m;++i) 
    {
        int a,b,c,d; 
        scanf("%d%d%d%d",&a,&b,&c,&d);          
        insert(a,b,0), insert(c,d,1);       
        int t1=0,t2=0,lcp=0;   
        while(t1<A[0].size()&&t2<A[1].size())  
        {  
            node a1=A[0][t1], a2=A[1][t2];         
            int uu=a1.u;     
            int vv=a2.u;     
            int lca;                  
            int tmp=min(sam::mx[lca=suffix_tree::LCA(uu,vv)], min(a1.len,a2.len));   
            lcp+=tmp;   
            if(tmp<min(a2.len,a2.len)) break;   
            else
            {       
                if(tmp==a1.len) ++t1;   
                else 
                {
                    A[0][t1].u=lca, A[0][t1].len=A[0][t1].len-a2.len;    
                }
                if(tmp==a2.len) ++t1;   
                else 
                {   
                    A[1][t2].u=lca, A[1][t2].len=A[1][t2].len-a1.len;   
                }
            }
        }     
        printf("%d\n",lcp);          
        A[0].clear(),A[1].clear();     
    }
    return 0; 
}