題目鏈接：點擊查看

題目大意：給定一個以1為根的n個節(jié)點的樹，每個點上有一個字母(a?z)，每個點的深度定義為該節(jié)點到1號節(jié)點路徑上的點數(shù)，每次詢問a,b查詢以a為根的子樹內深度為b的節(jié)點上的字母重新排列之后是否能構成回文串

題目分析：因為是關于每個子樹的詢問，所以可以試著用樹上啟發(fā)式合并考慮，具體問題需要具體分析，對于這個題目而言，主要是判斷以某個結點為根節(jié)點的子樹中，深度為d的結點中，出現(xiàn)次數(shù)為奇數(shù)的字母的個數(shù)必須小于等于1才行，那么我們只需實時維護每個字母的出現(xiàn)次數(shù)就好了，具體實現(xiàn)看代碼吧

最后有個細節(jié)需要說一下，就是在讀入字母的時候，如果用getchar或scanf讀的話，必須要自己寫一個Getchar函數(shù)才行，不然數(shù)據(jù)中會有n=1的情況，這個時候需要連續(xù)讀入兩個回車，不然就會RE

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e5+100;int w[N],deep[N],num[N],son[N],cnt[N][26];bool vis[N],ans[N];vector<int>node[N];vector<pair<int,int>>Q[N];//<id,deep>void dfs_son(int u,int dep) {son[u]=-1;num[u]=1;deep[u]=dep;for(auto v:node[u]){dfs_son(v,dep+1);num[u]+=num[v];if(son[u]==-1||num[v]>num[son[u]])son[u]=v;} }void cal(int u,int val) {cnt[deep[u]][w[u]]+=val;for(auto v:node[u]){if(vis[v])continue;cal(v,val);} }void dfs(int u,int keep) {for(auto v:node[u]){if(v==son[u])continue;dfs(v,0);}if(son[u]!=-1){dfs(son[u],1);vis[son[u]]=true;}cal(u,1);for(auto i:Q[u]){int id=i.first;int d=i.second;int sum=0;for(int j=0;j<26;j++)if(cnt[d][j]&1)sum++;if(sum>1)ans[id]=false;elseans[id]=true;}if(son[u]!=-1)vis[son[u]]=false;if(!keep)cal(u,-1); }char Getchar() {char ch;while(ch=getchar())if(ch!='\n'&&ch!=' ')return ch; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=2;i<=n;i++){int fa;scanf("%d",&fa);node[fa].push_back(i);}char ch;for(int i=1;i<=n;i++){ch=Getchar();w[i]=ch-'a';}for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);Q[a].push_back(make_pair(i,b));}dfs_son(1,1);dfs(1,1);for(int i=1;i<=m;i++){if(ans[i])puts("Yes");elseputs("No");}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 570D Tree Requests(树上启发式合并)的全部內容，希望文章能夠幫你解決所遇到的問題。

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