CF570D树的请求处理：深入探讨长链剖分技术的应用与优化

正题

题目链接:https://www.luogu.com.cn/problem/CF570D

题目大意

$n$个点的一棵树&＃xff0c;每个节点有字母&＃xff0c;每次询问一个节点$x$的子树中深度为$k$的所有点的字母能否经过重排构成一个回文串。

解题思路

首先把每个字母的奇偶状压一下
然后方法比较多&＃xff0c;一些就粗略的提一下

长链剖分

设fi,jf_{i,j}fi,j​表示节点$i$中距离$j$的节点状态&＃xff0c;然后这个是根据深度会转移的&＃xff0c;上长链剖分即可。

时间复杂度$O(n)$

二分$\&＃43;vector$

对于每个深度开一个$vector$按照$dfs$序列来存&＃xff0c;那么一个子树就是一个区间&＃xff0c;二分一下这个区间就好了。

时间复杂度$O(n\log n)$

线段树合并

就是把深度表示下标然后用线段树合并就好了&＃xff0c;如果要求在线那么空间的要求比较高

时间复杂度$O(n\log n)$

还有一写$dsu$之类的就和长链差不多了。

$code$

#include
#include
#include
#include
using namespace std;
const int N&＃61;1e6&＃43;10;
struct node{int to,next;
}a[N<<1];
int n,m,tot,dep[N],len[N],son[N];
int *f[N],*now,g[N],ls[N];
char s[N];bool ans[N];
vector<pair<int,int> > q[N];
void addl(int x,int y){a[&＃43;&＃43;tot].to&＃61;y;a[tot].next&＃61;ls[x];ls[x]&＃61;tot;return;
}
void dfs(int x){for(int i&＃61;ls[x];i;i&＃61;a[i].next){int y&＃61;a[i].to;dep[y]&＃61;dep[x]&＃43;1;dfs(y);if(len[y]>len[son[x]])son[x]&＃61;y;}len[x]&＃61;len[son[x]]&＃43;1;return;
}
bool ct(int x){if(x&＃61;&＃61;(x&-x))return 1;return 0;
}
void dp(int x){f[x][0]^&＃61;(1<<s[x]-&＃39;a&＃39;);if(son[x]){f[son[x]]&＃61;f[x]&＃43;1;dp(son[x]);}for(int i&＃61;ls[x];i;i&＃61;a[i].next){int y&＃61;a[i].to;if(y&＃61;&＃61;son[x])continue;f[y]&＃61;now;now&＃43;&＃61;len[y];dp(y);for(int j&＃61;1;j<&＃61;len[y];j&＃43;&＃43;)f[x][j]^&＃61;f[y][j-1];}for(int i&＃61;0;i<q[x].size();i&＃43;&＃43;){int dis&＃61;q[x][i].first,id&＃61;q[x][i].second;if(dis<dep[x]||dis>dep[x]&＃43;len[x])ans[id]&＃61;1;else ans[id]&＃61;ct(f[x][dis-dep[x]]);}return;
}
int main()
{scanf("%d%d",&n,&m);for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;){int x;scanf("%d",&x);addl(x,i);}scanf("%s",s&＃43;1);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){int x,y;scanf("%d%d",&x,&y);q[x].push_back(make_pair(y,i));}dep[1]&＃61;1;dfs(1);f[1]&＃61;now&＃61;g;now&＃43;&＃61;len[1];dp(1);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)puts(ans[i]?"Yes":"No");return 0;
}