題目鏈接：http://codeforces.com/contest/351/problem/D

題目大意：n個數，col[i]對應第i個數的顏色，并給你他們之間的樹形關系（以1為根），有m次詢問，每次給出vi,ki，要求找出以點vi為根的子樹上出現超過ki次的顏色數。

解題思路：這題顯然是可以用莫隊寫的，只要在開一個數組cnk[i]記錄出現次數超過i次的顏色數即可，但是要先進行“將樹化為線段的操作”，之前寫的一道線段樹也用了dfs序的方法使得多叉樹化為線段：鏈接，這里就不多說了。要注意的是使用dfs劃線的過程中記得要把對應序號的顏色也映射到線段上。

1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int N=1e5+5; 8 int num; 9 int unit; 10 int arr[N],col[N],cnt[N],cnk[N],res[N],Start[N],End[N],vis[N];//cnk[i]表示至少出現i次的顏色數 11 vector<int>v[N]; 12 13 struct node{ 14 int l,r,kj; 15 int id; 16 }q[N]; 17 18 //將樹化為區間 19 void dfs(int rt){ 20 Start[rt]=++num; 21 //**將對應序號的顏色映射到新的線段上 22 arr[num]=col[rt]; 23 vis[rt]=1; 24 for(int i=0;i<v[rt].size();i++){ 25 if(!vis[v[rt][i]]) 26 dfs(v[rt][i]); 27 } 28 End[rt]=num; 29 } 30 31 bool cmp(node a,node b){ 32 return a.l/unit==b.l/unit?a.r<b.r:a.l/unit<b.l/unit; 33 } 34 35 void add(int pos){ 36 cnt[arr[pos]]++; 37 cnk[cnt[arr[pos]]]++; 38 } 39 40 void remove(int pos){ 41 cnk[cnt[arr[pos]]]--; 42 cnt[arr[pos]]--; 43 } 44 45 int main(){ 46 int n,m; 47 scanf("%d%d",&n,&m); 48 unit=sqrt(n); 49 for(int i=1;i<=n;i++){ 50 scanf("%d",&col[i]); 51 } 52 for(int i=1;i<=n-1;i++){ 53 int a,b; 54 scanf("%d%d",&a,&b); 55 //**題目沒有直接說明a,b從屬關系所以建立雙向鄰接表 56 v[a].push_back(b); 57 v[b].push_back(a); 58 } 59 //以1為根 60 dfs(1); 61 62 for(int i=1;i<=m;i++){ 63 int vj,kj; 64 scanf("%d%d",&vj,&kj); 65 q[i].kj=kj; 66 q[i].id=i; 67 q[i].l=Start[vj]; 68 q[i].r=End[vj]; 69 } 70 sort(q+1,q+1+m,cmp); 71 int L=q[1].l,R=L-1; 72 for(int i=1;i<=m;i++){ 73 while(L>q[i].l) 74 add(--L); 75 while(L<q[i].l) 76 remove(L++); 77 while(R<q[i].r) 78 add(++R); 79 while(R>q[i].r) 80 remove(R--); 81 res[q[i].id]=cnk[q[i].kj]; 82 } 83 for(int i=1;i<=m;i++){ 84 printf("%d\n",res[i]); 85 } 86 } 87

?

轉載于:https://www.cnblogs.com/fu3638/p/7201252.html

總結

以上是生活随笔為你收集整理的Codeforces 375D - Tree and Queries(dfs序+莫队)的全部內容，希望文章能夠幫你解決所遇到的問題。

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