570-D 题目大意
给定一棵\(n\)个节点的树,根节点为\(1\),每个节点上有一个小写字母\(ch\)。定义节点\(x\)的深度为\(x\)到根节点的路径上的节点数量。\(q\)次询问,每次询问查询以\(x\)为根的子树之中所有深度为\(d\)的节点上字母重排之后是否可以构成一个回文串。
Solution
对于一组能够拼凑出回文串的字符,其中数量为奇数的字符个数不超过\(1\)。因为字符集大小为\(26\),我们可以用一个二进制数来表示各个字符出现次数是奇数还是偶数。对于节点\(x\),我只需要把其各个子节点中的信息异或起来就能够得到整个以\(x\)为根的子树中的信息。
对于节点\(x\),用\(p[x][d]\)来记录在当前子树中,深度为\(d\)的字符出现情况,每次递归子树时进行暴力合并,复杂度最坏为\(O(n^2)\),考虑优化合并的过程。
\(dsu{\;}on{\;}tree\)是常用的合并树上信息的算法,每次枚举完\(x\)的儿子节点\(y\),就比较\(p[x]\)与\(p[y]\)两个集合的大小,把更大的集合交换给\(p[x]\),再把小的集合暴力合并到\(p[x]\)中。
时间复杂度\(O(nlog^{2}n)\),这里不用的\(map\)的话复杂度能够降为\(O(nlogn)\),复杂度的具体证明请自行百度。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve(){
int n,q;
cin>>n>>q;
vector<vector<int>> e(n+1);
for(int i=2;i<=n;i++){
int x;
cin>>x;
e[x].push_back(i);
}
string s;
cin>>s;
vector<vector<array<int,2>>> Q(n+1);
for(int i=0;i<q;i++){
int x,d;
cin>>x>>d;
Q[x].push_back({d,i});
}
vector<map<int,int>> p(n+1);
vector<int> ans(q);
function<void(int,int)> dfs=[&](int x,int depth){
for(auto y:e[x]){
dfs(y,depth+1);
if(p[y].size()>p[x].size()) swap(p[x],p[y]);
for(auto &[d,w]:p[y]){
p[x][d]^=w;
}
}
p[x][depth]=(1<<(s[x-1]-'a'));
for(auto [d,i]:Q[x]){
if(!p[x].count(d)){
ans[i]=1;
}else if(__builtin_popcount(p[x][d])<=1){
ans[i]=1;
}
}
};
dfs(1,1);
for(int i=0;i<q;i++){
if(ans[i]){
cout<<"Yes"<<'\n';
}else{
cout<<"No"<<'\n';
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
标签:int,复杂度,570,合并,CF,vector,启发式,节点
From: https://www.cnblogs.com/fengxue-K/p/17978426