Bingbong的回文路径

Here

利用回文串，从左往右与从右往左的hash值相同来判断
从左往右，例： $bccb=>p^3+2p^2+2p+1$
从右往左，例： $bccb=>1+2p+2p^2+p^3$
由于在树上，考虑建两颗树，一颗根为最高位（up），一棵根为最低位（down)
考虑bccb(1,2,3,4)这个
$(4,3,2,1)=>down(3,2,1)*p^{(weiup=1)}+up(4)$
$down(3,2,1)=>[(p^3+2p^2+2p+3)-(3)]*(1/p)=p^2+2p+2$ ，即bcc
$up(4)=>(3p^2+2p+1)-(3p+2)*(p)=1$ ，即b
$(4,3,2,1)=(p^2+2p+2)*p+1=p^3+2p^2+2p+1$
所以设在树上两点 $(u,v),LCA=x$
$v\rightarrow x\rightarrow u$
$down(x,u)=[down(u)-down(fa[x])]*inv(dep[x])$ (乘inv使x为最低位)
$up(x,v)=up(v)-up(x)*(dep[v]-dep[x])$
$weiup=dep[v]-dep[x]$
$v\rightarrow x\rightarrow u=down(x,u)*p^{weiup}+up(x,v)$
$u\rightarrow x\rightarrow v$ ，swap(u,v)即可
为保证hash的正确性，采用双哈希， $base=(29,131),mod=(1e9+7,1e9+9)$


import java.io.*;
import java.math.BigInteger;
import java.util.*;


//implements Runnable
public class Main {
    static long md1=(long)1e9+7;
    static long md2=(long)1e9+9;
    static long Linf=Long.MAX_VALUE/2;
    static int inf=Integer.MAX_VALUE/2;
    static int N=200010;
    static int n=0;
    static int m=0;


    static
    class M{
        long x,y;
        public M(){};
        public M(long u,long v){
            x=u;y=v;
        }
    }
    static M mul(M a,M b){
        return new M(a.x*b.x%md1,a.y*b.y%md2);
    }
    static M add(M a,M b){
        return new M((a.x+b.x)%md1,(a.y+b.y)%md2);
    }
    static M sub(M a,M b){
        return new M((a.x-b.x+md1)%md1,(a.y-b.y+md2)%md2);
    }
    static M[] inv;
    static M[] fac;
    static M base=new M(29,131);
    static long qm2(long a,long b,long md){
        long res=1;
        while(b>0){
            if((b&1)==1)res=res*a%md;
            a=a*a%md;
            b>>=1;
        }
        return res;
    }
    static void getFac(){
       fac[0]=new M(1,1);
       up[0]=new M(0,0);
       down[0]=new M(0,0);
       for(int i=1;i<=n;++i){
           fac[i]=mul(fac[i-1],base);
       }
       inv[n]=new M();
       inv[n].x=qm2(fac[n].x,md1-2,md1);
       inv[n].y=qm2(fac[n].y,md2-2,md2);
       for(int i=n-1;i>=0;i--){
           inv[i]=mul(inv[i+1],base);
       }
    }
    static
    class Edge{
        int fr,to,nxt;
        public Edge(int u,int v){
            fr=u;to=v;
        }
    }
    static Edge[] e;
    static int[] head;
    static int cnt=0;
    static void addEdge(int fr,int to){
        cnt++;
        e[cnt]=new Edge(fr,to);
        e[cnt].nxt=head[fr];
        head[fr]=cnt;
    }
    static int[] fa;
    static int[] son;
    static int[] siz;
    static int[] dep;
    static int[] top;
    static M[] down;
    static M[] up;
    static int[] a;
    static void dfs1(int x,int f){
        siz[x]=1;dep[x]=dep[f]+1;fa[x]=f;
        up[x]=add(mul(up[f],base),new M(a[x],a[x]));
        down[x]=add(down[f],mul(new M(a[x],a[x]),fac[dep[x]]));
        for(int i=head[x];i>0;i=e[i].nxt){
            int v=e[i].to;
            if(v==f)continue;
            dfs1(v,x);
            siz[x]+=siz[v];
            if(siz[son[x]]<siz[v])son[x]=v;
        }
    }
    static void dfs2(int x,int tp){
        top[x]=tp;
        if(son[x]!=0)dfs2(son[x],tp);
        for(int i=head[x];i>0;i=e[i].nxt){
            int v=e[i].to;
            if(v==fa[x]||v==son[x])continue;
            dfs2(v,v);
        }
    }
    static int LCA(int x,int y){
        while(top[x]!=top[y]){
            if(dep[top[x]]>dep[top[y]]){
                int t=x;x=y;y=t;
            }
            y=fa[top[y]];
        }
        if(dep[x]>dep[y]){
            int t=x;x=y;y=t;
        }
        return x;
    }
    static M getHash(int u,int v,int x){

        M ux=mul(sub(down[u],down[fa[x]]),inv[dep[x]]);
        M xv=sub(up[v],mul(up[x],fac[dep[v]-dep[x]]));
        return add(mul(ux,fac[dep[v]-dep[x]]),xv);//从右上左下
    }
    static void getPre(){
        fac=new M[n+1];
        inv=new M[n+1];
        fa=new int[n+1];
        son=new int[n+1];
        siz=new int[n+1];
        dep=new int[n+1];
        top=new int[n+1];
        head=new int[n+1];
        e=new Edge[2*n+10];
        cnt=0;
        down=new M[n+1];//rha
        up=new M[n+1];//ha
        a=new int[n+1];
    }
    static void solve() throws Exception{
        AReader input=new AReader();
//        String fileName="";
//		Scanner input=new Scanner(new FileReader(fileName));

//        BufferedReader input = new BufferedReader(new FileReader(fileName));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        String al="abcdefghijklmnopqrstuvwxyz";
        char[] ac=al.toCharArray();
        n=input.nextInt();
        getPre();
        getFac();
        String string=" "+input.next();
        char[] s=string.toCharArray();
        for(int i=1;i<=n;++i){
            a[i]=s[i]-'a'+1;
        }
        for(int i=1;i<=n;++i){
            int x=input.nextInt();
            addEdge(x,i);
            addEdge(i,x);
        }
        dep[0]=-1;
        dfs1(1,0);
        dfs2(1,1);
        m=input.nextInt();
        while(m>0){
            m--;
            int x=input.nextInt();
            int y=input.nextInt();
            int p=LCA(x,y);
            M rtol=getHash(x,y,p);
            M ltor=getHash(y,x,p);
            if(rtol.x==ltor.x&&rtol.y==ltor.y)out.println("YES");
            else out.println("NO");
        }
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        solve();
    }
    //	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Tx2(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}
    static
    class AReader{
        BufferedReader bf;
        StringTokenizer st;

        public AReader(){
            bf=new BufferedReader(new InputStreamReader(System.in));
            st=new StringTokenizer("");
        }
        public String nextLine() throws IOException{
            return bf.readLine();
        }
        public String next() throws IOException{
            while(!st.hasMoreTokens()){
                st=new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }
        public char nextChar() throws IOException{
            //确定下一个token只有一个字符的时候再用
            return next().charAt(0);
        }
        public int nextInt() throws IOException{
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException{
            return Long.parseLong(next());
        }
        public double nextDouble() throws IOException{
            return Double.parseDouble(next());
        }
        public float nextFloat() throws IOException{
            return Float.parseFloat(next());
        }
        public byte nextByte() throws IOException{
            return Byte.parseByte(next());
        }
        public short nextShort() throws IOException{
            return Short.parseShort(next());
        }
        public BigInteger nextBigInteger() throws IOException{
            return new BigInteger(next());
        }
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/566816.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！