Codeforces

Luogu

分析

考虑对原树树链剖分,则两条路径都拆成了 $\mathcal{O}(\log n)$ 个区间。

每次取最前面的区间出来比较,如果相同则消掉一个区间,否则答案在该区间内,二分即可。

问题在于如何求出某条重链的哈希值。因为重链的 DFS 序是连续的一段,因此可以将树按 DFS 序拍成序列,然后正反各做一遍哈希,则一条重链的哈希值相当于某个区间的哈希值。

代码实现有些复杂。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

struct Hash { int x,y; };
const int mod1=1e9+7,mod2=1e9+9;
const Hash BASE=(Hash){2333,6666};
Hash operator +(Hash x,int y) {
    return (Hash){(x.x+y)%mod1,(x.y+y)%mod2};
}
Hash operator +(Hash x,Hash y) {
    return (Hash){(x.x+y.x)%mod1,(x.y+y.y)%mod2};
}
Hash operator -(Hash x,Hash y) {
    return (Hash){(x.x-y.x+mod1)%mod1,(x.y-y.y+mod2)%mod2};
}
Hash operator *(Hash x,Hash y) {
    return (Hash){(int)(1ll*x.x*y.x%mod1),(int)(1ll*x.y*y.y%mod2)};
}
bool operator ==(Hash x,Hash y) { return x.x==y.x&&x.y==y.y; }

const int N=300000+10;

int n,m; char s[N];

Hash pw[N],h1[N],h2[N];
inline Hash gethash(int op,int p,int l) {
    if (op) return h1[p+l-1]-h1[p-1]*pw[l];
    else return h2[p-l+1]-h2[p+1]*pw[l];
}

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dep[N],fa[N],sz[N],hson[N],top[N],dfn[N],pos[N],tim=0;
inline void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim,pos[tim]=u;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
inline int getlca(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

inline vector<pair<int,int> > divide(int u,int v) {
    int t=getlca(u,v);
    vector<pair<int,int> > x,y;
    while (dep[top[u]]>dep[t])
        x.push_back(make_pair(u,top[u])),u=fa[top[u]];
    x.push_back(make_pair(u,t));
    while (dep[top[v]]>dep[t])
        y.push_back(make_pair(top[v],v)),v=fa[top[v]];
    if (v!=t) y.push_back(make_pair(hson[t],v));
    while (y.size()) x.push_back(y.back()),y.pop_back();
    return x;
}

int main() {
    n=read(); scanf("%s",s+1);
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    pw[0]=(Hash){1,1};
    for (re int i=1;i<=n;++i) pw[i]=pw[i-1]*BASE;
    dfs1(1,0),dfs2(1,1);
    for (re int i=1;i<=n;++i) h1[i]=h1[i-1]*BASE+s[pos[i]];
    for (re int i=n;i>=1;--i) h2[i]=h2[i+1]*BASE+s[pos[i]];
    m=read();
    while (m--) {
        int a=read(),b=read(),c=read(),d=read(),ans=0;
        vector<pair<int,int> > x=divide(a,b),y=divide(c,d);
        for (re int i=0,j=0;i<x.size()&&j<y.size();) {
            int x1=dfn[x[i].first],y1=dfn[x[i].second];
            int x2=dfn[y[j].first],y2=dfn[y[j].second];
            int len=min(abs(x1-y1),abs(x2-y2))+1;
            Hash hx=gethash(x1<y1,x1,len),hy=gethash(x2<y2,x2,len);
            if (hx==hy) {
                if (len==abs(x1-y1)+1) ++i;
                else x[i].first=pos[dfn[x[i].first]+(x1<y1?len:-len)];
                if (len==abs(x2-y2)+1) ++j;
                else y[j].first=pos[dfn[y[j].first]+(x2<y2?len:-len)];
                ans+=len;
            } else {
                int L=1,R=len;
                while (L<R) {
                    int mid=(L+R)>>1;
                    hx=gethash(x1<y1,x1,mid),hy=gethash(x2<y2,x2,mid);
                    if (hx==hy) L=mid+1;
                    else R=mid;
                }
                ans+=L-1; break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2020 年 03 月 15 日 10 : 27 PM