在一棵无限延伸的二叉树上，缠绕着一株蔷薇花，它上面一共开了 \(n\) 朵蔷薇，构成了一个包含根节点的连通块。咒语是一个长为 \(m\) 的 \(01\) 串，若对一朵蔷薇念动咒语，则会有魔术回路沿着咒语向下传达。魔术回路会逐个按照咒语的每一个字符，若为 \(0\) 则传达到左子，若为 \(1\) 则传达到右子，如不存在则魔术失败。对于每朵蔷薇，问若对其念动咒语，魔术是否会失败，如成功则传达到哪朵玫瑰？
\(1\leq n,m\leq 3\cdot 10^5\)
一开始以为是一个数据结构，考虑根号分段，将 \(m\) 分成 \(\sqrt m\) 段，记录每个节点从指令 \(\sqrt m\) 个段开始走 \(\sqrt m\) 步能走到的节点 . 但是，发现我无法 \(\mathrm O(n\sqrt n)\) 的时间求出，弃掉了.
接着，我发现如果节点往下走 \(m\) 个，有多种选择，但是如果是节点往上走 \(m\) 个，只会有 \(1\) 种选择 .
如果 \(x\) 向上走 \(m\) 步的情况和给定 \(01\) 串相同，那么，向上走到的那个节点 \(y\) 向下走 \(m\) 步之后走到的节点就是 \(x\) .
考虑对每个节点向上走 \(\sqrt m\) 步的指令在指令 \(\sqrt m\) 个段中的位置 .
不用一一比对，可以算出一个哈希值，然后跟 \(\sqrt m\) 段的哈希值比对，这样，\(\mathrm O(n\sqrt m)\) 地求出 .
这样，往上跳 \(\sqrt m\) 就可以找到上面的节点 .
但是，受人提醒，发现还可以再优化 .
抛弃这题是一个数据结构的局限性，考虑求出节点 \(x\) 向上 \(m\) 步的哈希值，如果与指令的哈希值相等，那么，向上 \(m\) 步所到达的位置 \(y\) 线下走 \(m\) 步得到的就是 \(x\) .
现在要解决的问题就是如何求出每个节点上面 \(m\) 级的祖先 .
因为 \(m\) 固定，考虑在 dfs 的同时维护一个双端队列，保存路径，如果向下走的步数超过 \(m\) 层了，则弹出栈顶的元素，如果为 \(0\) ，则向左儿子走一步，否则，向右儿子走一步 .
那么，上面 \(m\) 个祖先的操作序列的哈希值也是一样，要维护一个双端队列，保存路径 . 超过 \(m\) 层的时候，弹出栈顶的元素，如果为 \(1\) ，就要哈希值就要减掉对应位的值 .
这两个 dfs 一定要记得回溯 .
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
int res=0;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return res;
}
inline void print(int res){
if(res==0){
putchar('0');
return;
}
int a[10],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
int n,m;
int a[300010];
int fa[300010],son[300010][2];
int dep[300010];
int anc[300010];
int Anc=0;
deque<int>q;
void get_anc(int x){
if(son[x][0]!=-1){
q.push_back(0);
dep[son[x][0]]=dep[x]+1;
int tmp,t;
if(dep[son[x][0]]==m)
anc[son[x][0]]=Anc;
if(dep[son[x][0]]>m){
tmp=Anc,t=q.front();
Anc=son[Anc][t];
anc[son[x][0]]=Anc;
q.pop_front();
}
get_anc(son[x][0]);
if(dep[son[x][0]]>m){
Anc=tmp;
q.push_front(t);
}
q.pop_back();
}
if(son[x][1]!=-1){
q.push_back(1);
dep[son[x][1]]=dep[x]+1;
int tmp,t;
if(dep[son[x][1]]==m)
anc[son[x][1]]=Anc;
if(dep[son[x][1]]>m){
tmp=Anc,t=q.front();
Anc=son[Anc][t];
anc[son[x][1]]=Anc;
q.pop_front();
}
get_anc(son[x][1]);
if(dep[son[x][1]]>m){
Anc=tmp;
q.push_front(t);
}
q.pop_back();
}
}
class Hash{
public:
int mod,p[300010];
int val,tar;
void get_p(){
p[0]=1;
for(int i=1;i<300010;i++){
p[i]=p[i-1]*2%mod;
}
}
}H[3];
int ans[300010];
void dfs(int x){
if(dep[x]>=m){
if(H[0].tar==H[0].val&&H[1].tar==H[1].val&&H[2].val==H[2].tar){
ans[anc[x]]=x;
}
}
if(son[x][0]!=-1){
q.push_back(0);
int tmp[3];
for(int i=0;i<3;i++){
tmp[i]=H[i].val;
H[i].val=(H[i].val<<1)%H[i].mod;
if(dep[son[x][0]]>m){
H[i].val=(H[i].val-H[i].p[m]*q.front()+H[i].mod)%H[i].mod;
}
}
int t;
if(dep[son[x][0]]>m){
t=q.front();
q.pop_front();
}
dfs(son[x][0]);
if(dep[son[x][0]]>m){
q.push_front(t);
}
for(int i=0;i<3;i++)H[i].val=tmp[i];
q.pop_back();
}
if(son[x][1]!=-1){
q.push_back(1);
int tmp[3];
for(int i=0;i<3;i++){
tmp[i]=H[i].val;
H[i].val=((H[i].val<<1)%H[i].mod+1)%H[i].mod;
if(dep[son[x][1]]>m){
H[i].val=(H[i].val-H[i].p[m]*q.front()+H[i].mod)%H[i].mod;
}
}
int t;
if(dep[son[x][1]]>m){
t=q.front();
q.pop_front();
}
dfs(son[x][1]);
if(dep[son[x][1]]>m){
q.push_front(t);
}
for(int i=0;i<3;i++)H[i].val=tmp[i];
q.pop_back();
}
}
int main(){
freopen("rose.in","r",stdin);
freopen("rose.out","w",stdout);
n=read();
memset(fa,-1,sizeof(fa));
memset(son,-1,sizeof(son));
fa[0]=-1;
for(int i=0;i<n-1;i++){
int u=read()-1,v=read()-1,type=read();
son[u][type]=v;
}
m=read();
for(int i=0;i<m;i++)a[i]=read();
memset(anc,-1,sizeof(anc));
get_anc(0);
H[0].mod=998244353;H[1].mod=1000000007;H[2].mod=1000000009;
for(int i=0;i<3;i++){
H[i].get_p();
H[i].val=H[i].tar=0;
}
for(int i=0;i<3;i++)for(int j=0;j<m;j++){
H[i].tar=((H[i].tar<<1)%H[i].mod+a[j])%H[i].mod;
}
while(!q.empty())q.pop_back();
memset(ans,-1,sizeof(ans));
dfs(0);
for(int i=0;i<n;i++){
print(ans[i]+1);
putchar(' ');
}
putchar('\n');
return 0;
}
/*inline? ll or int? size? min max?*/