正題

題目鏈接:https://www.luogu.com.cn/problem/CF570D

---

題目大意

$n$個點的一棵樹，每個節(jié)點有字母，每次詢問一個節(jié)點$x$的子樹中深度為$k$的所有點的字母能否經(jīng)過重排構(gòu)成一個回文串。

---

解題思路

首先把每個字母的奇偶狀壓一下
然后方法比較多，一些就粗略的提一下

長鏈剖分

設(shè)$f_{i,j}$表示節(jié)點$i$中距離$j$的節(jié)點狀態(tài)，然后這個是根據(jù)深度會轉(zhuǎn)移的，上長鏈剖分即可。

時間復(fù)雜度$O(n)$

二分$+vector$

對于每個深度開一個$vector$按照$dfs$序列來存，那么一個子樹就是一個區(qū)間，二分一下這個區(qū)間就好了。

時間復(fù)雜度$O(n\log n)$

線段樹合并

就是把深度表示下標然后用線段樹合并就好了，如果要求在線那么空間的要求比較高

時間復(fù)雜度$O(n\log n)$

還有一寫$dsu$之類的就和長鏈差不多了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=1e6+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[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){for(int i=ls[x];i;i=a[i].next){int y=a[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]^=(1<<s[x]-'a');if(son[x]){f[son[x]]=f[x]+1;dp(son[x]);}for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==son[x])continue;f[y]=now;now+=len[y];dp(y);for(int j=1;j<=len[y];j++)f[x][j]^=f[y][j-1];}for(int i=0;i<q[x].size();i++){int dis=q[x][i].first,id=q[x][i].second;if(dis<dep[x]||dis>dep[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 i=2;i<=n;i++){int x;scanf("%d",&x);addl(x,i);}scanf("%s",s+1);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);q[x].push_back(make_pair(y,i));}dep[1]=1;dfs(1);f[1]=now=g;now+=len[1];dp(1);for(int i=1;i<=m;i++)puts(ans[i]?"Yes":"No");return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF570D-Tree Requests【长链剖分】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。