題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4358

解題思路：用dfs求出整棵樹的dfs序列，這樣以u為根節點的子樹就轉化到相對應的區間上了。由于是區間不修改查詢問題，這個時候就可以用莫隊算法了。

#pragma comment(linker, "/STACK:16777216") #include<iostream> #include<cstdio> #include<cstring> #include<map> #include<algorithm> using namespace std;const int maxn = 100005; int n,m,k,cnt,head[maxn],w[maxn],val[maxn]; int block,tot,L[maxn],R[maxn]; int res[maxn]; struct Edge {int to,next; }edge[maxn<<1]; struct Query {int l,r,id;bool operator < (const Query rhs) const{if(l / block == rhs.l / block)return r < rhs.r;return l / block < rhs.l / block;} }q[maxn<<1]; map<int,int> Map;void addedge(int u,int v) {edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++; }void dfs(int u,int fa) {L[u] = ++tot;val[tot] = w[u];for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(v == fa) continue;dfs(v,u);}R[u] = tot; }void solve() {block = sqrt(tot + 0.5);sort(q+1,q+1+m);int ans = 0,l = 1,r = 0;for(int i = 1; i <= m; i++){while(r < q[i].r){r++;Map[val[r]]++;if(Map[val[r]] == k) ans++;if(Map[val[r]] == k + 1) ans--;}while(r > q[i].r){if(Map[val[r]] == k) ans--;Map[val[r]]--;if(Map[val[r]] == k) ans++;r--;}while(l < q[i].l){if(Map[val[l]] == k) ans--;Map[val[l]]--;if(Map[val[l]] == k) ans++;l++;}while(l > q[i].l){l--;Map[val[l]]++;if(Map[val[l]] == k) ans++;if(Map[val[l]] == k + 1) ans--;}res[q[i].id] = ans;} }int main() {int t,u,v,cas = 1;scanf("%d",&t);while(t--){tot = cnt = 0;memset(head,-1,sizeof(head));Map.clear();scanf("%d%d",&n,&k);for(int i = 1; i <= n; i++)scanf("%d",&w[i]);for(int i = 1; i < n; i++){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,-1);scanf("%d",&m);for(int i = 1; i <= m; i++){scanf("%d",&u);q[i].l = L[u];q[i].r = R[u];q[i].id = i;}solve();printf("Case #%d:\n",cas++);for(int i = 1; i <= m; i++)printf("%d\n",res[i]);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4358(莫队算法+dfs序列)的全部內容，希望文章能夠幫你解決所遇到的問題。

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