← 返回题目列表

AtCoder · ijpc2015_j

E. 忠实

中文机器翻译题面 查看原题

問題文

IOI2015举办地阿拉木图过去曾名为韦尔内伊。
显然,它在俄语中的意思是“忠诚”或“值得信赖”。 。
乔伊西诺姐姐听了这话,决定测试下属对自己的忠诚度。

首先,我们准备一棵树X和一棵树Y。每个顶点是0不同编号的点最多为(木の頂点数-1)和从“a”到“j”的一个小写字母。

执行以下操作。 执行Q次。 树 X 上直至

  • A不同编号的点最多为B的路径(A,B交换上面的两个字母。 如果替换路径上的
      例如,'a'和'b', 树 Y 上直至'a'是'b'变为 答案是正确的,因为'b'是'a'变为。 给定了
  • A不同编号的点最多为B的路径(A,B交换上面的两个字母。 如果替换路径上的
      例如,'a'和'b', 树 Y 上直至'a'是'b'变为 答案是正确的,因为'b'是'a'变为。 给定了
  • 树XA不同编号的点最多为B的路径(A,B上面的字母串和树 Y。C不同编号的点最多为D的路径(C,D) 回答上面的字母串是否完全匹配。 执行
  • a查询后立即返回状态。
      但是,(处理此查询之前处理的查询数)≥a≧0。

  • 制限

    1≦Q≦10^5
    1≦(木Xの頂点数)≦10^5
    1≦(木Yの頂点数)≦10^5

    配点

    • 该问题没有部分分数。如果您正确回答所有测试用例100点。

    入力

    输入是按以下格式从标准输入给出的。

    木Xについてのデータ
    木Yについてのデータ
    Q
    クエリ1
    クエリ2
    .
    .
    .
    クエリQ
    
     首先,给出关于树X的数据。
     接下来,给出关于树Y的数据。
     接下来是一个整数,表示查询的数量。Q在一行中给出。 下一个Q行表示每个查询。
     每棵树的数据按以下格式给出。
    N
    s
    a_1 b_1
    a_2 b_2
    .
    .
    .
    a_N-1 b_N-1
    
     数据中的第一行显示树中的顶点数。N作为整数给出。
     下一行,长度 给出N的字符串 s。这个字符串的i+1文字目(0≦i<N) 指写在树顶部 i 的小写字母。
     接下来的 N-1 行中的每一行代表树的一条边。
     a_i和b_i是顶点a_i和顶点 这意味着b_i(0<i≦N-1之间有一条边。

     每个查询都从一行给出。 首先是一个整数,表示查询的类型 当t。  
       
    • t为0时
       后面是一个由空格分隔的整数。a,b和小写字母c,d按此顺序给出。 这是树的顶部a,b( 之间的路径上的顶点a,b)在每种情况下, 如果写c意思是重写为d到,d意思是重写为c。 当  
    •  
    • t为1时
       后面是一个由空格分隔的整数。a,b和小写字母c,d按此顺序给出。 这是Y树的顶部 当a,b( 之间的路径上的顶点a,b)在每种情况下, 如果写c意思是重写为d到,d意思是重写为c。 当  
    •  
    • t为2时
       后面是一个由空格分隔的整数。a,b和小写字母c,d按此顺序给出。 这是(树的顶点a,b( 之间的路径上的顶点a,b包括),a按顺序排列的字符串)和(树Y的顶点 意思是回答字符串(从c,d( 之间的路径上的顶点c,d包括),c开始按顺序排列的字符串)是否匹配。 当  
    •  
    • t为3时 给出了
       后面是一个由空格分隔的整数。a。 这意味着树 X 和树 Y 是a表示处理完查询后立即返回到该情况。  

    出力

     在每个查询中 当t为2时,如果字符串匹配"YES",如果不匹配 在一行上输出"NO"。
     不要忘记整个输入末尾的换行符。


    入力例1

    4
    ckdl
    0 2
    0 1
    1 3
    4
    lckd
    2 1
    1 3
    2 0
    4
    2 2 3 3 0
    2 2 3 0 3
    2 3 2 0 3
    2 3 2 3 0
    

    出力例1

    YES
    NO
    YES
    NO