网站设计需要哪些技能,上海人才引进政策,想找人做网站 要怎么选择,东营新闻联播在线直播今晚正题
题目链接:https://www.luogu.com.cn/problem/CF570D 题目大意 nnn个点的一棵树#xff0c;每个节点有字母#xff0c;每次询问一个节点xxx的子树中深度为kkk的所有点的字母能否经过重排构成一个回文串。 解题思路
首先把每个字母的奇偶状压一下 然后方法比较多#x…正题
题目链接:https://www.luogu.com.cn/problem/CF570D 题目大意
nnn个点的一棵树每个节点有字母每次询问一个节点xxx的子树中深度为kkk的所有点的字母能否经过重排构成一个回文串。 解题思路
首先把每个字母的奇偶状压一下 然后方法比较多一些就粗略的提一下
长链剖分
设fi,jf_{i,j}fi,j表示节点iii中距离jjj的节点状态然后这个是根据深度会转移的上长链剖分即可。
时间复杂度O(n)O(n)O(n)
二分vectorvectorvector
对于每个深度开一个vectorvectorvector按照dfsdfsdfs序列来存那么一个子树就是一个区间二分一下这个区间就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn)
线段树合并
就是把深度表示下标然后用线段树合并就好了如果要求在线那么空间的要求比较高
时间复杂度O(nlogn)O(n\log n)O(nlogn)
还有一写dsudsudsu之类的就和长链差不多了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1e610;
struct node{int to,next;
}a[N1];
int n,m,tot,dep[N],len[N],son[N];
int *f[N],*now,g[N],ls[N];
char s[N];bool ans[N];
vectorpairint,int q[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x){for(int ils[x];i;ia[i].next){int ya[i].to;dep[y]dep[x]1;dfs(y);if(len[y]len[son[x]])son[x]y;}len[x]len[son[x]]1;return;
}
bool ct(int x){if(x(x-x))return 1;return 0;
}
void dp(int x){f[x][0]^(1s[x]-a);if(son[x]){f[son[x]]f[x]1;dp(son[x]);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yson[x])continue;f[y]now;nowlen[y];dp(y);for(int j1;jlen[y];j)f[x][j]^f[y][j-1];}for(int i0;iq[x].size();i){int disq[x][i].first,idq[x][i].second;if(disdep[x]||disdep[x]len[x])ans[id]1;else ans[id]ct(f[x][dis-dep[x]]);}return;
}
int main()
{scanf(%d%d,n,m);for(int i2;in;i){int x;scanf(%d,x);addl(x,i);}scanf(%s,s1);for(int i1;im;i){int x,y;scanf(%d%d,x,y);q[x].push_back(make_pair(y,i));}dep[1]1;dfs(1);f[1]nowg;nowlen[1];dp(1);for(int i1;im;i)puts(ans[i]?Yes:No);return 0;
}
