第一题扫2遍，第一遍计算每个字符的最终位置，第二遍直接移位。

第二题dp。

第三题如果只询问一次且要输出路径的话暴力向上爬就好了，如果多次询问只询问路径长度就预处理下深度求LCA吧。