HDU 4358 莫队算法+dfs序+离散化

Boring counting

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 98304/98304 K (Java/Others)
Total Submission(s): 2808 Accepted Submission(s): 826

Problem Description

In this problem we consider a rooted tree with N vertices. The vertices are numbered from 1 to N, and vertex 1 represents the root. There are integer weights on each vectice. Your task is to answer a list of queries, for each query, please tell us among all the vertices in the subtree rooted at vertice u, how many different kinds of weights appear exactly K times?

Input

The first line of the input contains an integer T( T<= 5 ), indicating the number of test cases.
For each test case, the first line contains two integers N and K, as described above. ( 1<= N <= 10⁵, 1 <= K <= N )
Then come N integers in the second line, they are the weights of vertice 1 to N. ( 0 <= weight <= 10⁹ )
For next N-1 lines, each line contains two vertices u and v, which is connected in the tree.
Next line is a integer Q, representing the number of queries. (1 <= Q <= 10⁵)
For next Q lines, each with an integer u, as the root of the subtree described above.

Output

For each test case, output "Case #X:" first, X is the test number. Then output Q lines, each with a number -- the answer to each query.

Seperate each test case with an empty line.

Sample Input

1
3 1
1 2 2
1 2
1 3
3
2
1
3

Sample Output

Case #1:

Author

fish@UESTC_Oblivion

Source

2012 Multi-University Training Contest 6

题意：给你一个树每个节点都有一个权值 q个询问问x的子树中有多少种不同的权值出现了k次

题解：第一题莫队莫队算法正如莫涛本人而言这种方法是处理一类无修改的离线区间询问问题的 dfs序将子树的问题转换为区间问题

之后就是莫队的处理，只是一个神奇的算法，在我看来就是一种有技巧的暴力。另外还要注意对权值的离散化。PE orzz

  1 /******************************
  2 code by drizzle
  3 blog: www.cnblogs.com/hsd-/
  4 ^ ^    ^ ^
  5  O      O
  6 ******************************/
  7 #include<bits/stdc++.h>
  8 #include<map>
  9 #include<set>
 10 #include<cmath>
 11 #include<queue>
 12 #include<bitset>
 13 #include<math.h>
 14 #include<vector>
 15 #include<string>
 16 #include<stdio.h>
 17 #include<cstring>
 18 #include<iostream>
 19 #include<algorithm>
 20 #pragma comment(linker, "/STACK:102400000,102400000")
 21 using namespace std;
 22 #define  A first
 23 #define B second
 24 const int mod=1000000007;
 25 const int MOD1=1000000007;
 26 const int MOD2=1000000009;
 27 const double EPS=0.00000001;
 28 typedef __int64 ll;
 29 const ll MOD=1000000007;
 30 const int INF=1000000010;
 31 const ll MAX=1ll<<55;
 32 const double eps=1e-5;
 33 const double inf=~0u>>1;
 34 const double pi=acos(-1.0);
 35 typedef double db;
 36 typedef unsigned int uint;
 37 typedef unsigned long long ull;
 38 int T;
 39 int n,k,w[100005],v[100005],vv[100005],x,y,q;
 40 int in[100005],out[100005];
 41 int pre[100005];
 42 int pos[100005];
 43 int re[100005];
 44 int sum[100005];
 45 int dfn=0;
 46 int ans;int nedge=0;
 47 struct node
 48 {
 49     int pre,ed;
 50 }N[200005];
 51 struct query
 52 {
 53     int id;
 54     int l,r;
 55 }M[100005];
 56 void add(int st,int ed )
 57 {
 58     nedge++;
 59     N[nedge].ed=ed;
 60     N[nedge].pre=pre[st];
 61     pre[st]=nedge;
 62 }
 63 void getdfs(int now,int fa)
 64 {
 65     in[now]=++dfn;
 66     for(int i=pre[now];i;i=N[i].pre)
 67     {
 68         if(N[i].ed!=fa)
 69         {
 70             getdfs(N[i].ed,now);
 71         }
 72     }
 73     out[now]=dfn;
 74 }
 75 void init()
 76 {
 77     nedge=0;
 78     memset(pre,0,sizeof(pre));
 79     dfn=0;
 80     ans=0;
 81     memset(sum,0,sizeof(sum));
 82     memset(N,0,sizeof(N));
 83     memset(M,0,sizeof(M));
 84     memset(re,0,sizeof(re));
 85     memset(pos,0,sizeof(pos));
 86     memset(in,0,sizeof(in));
 87     memset(out,0,sizeof(out));
 88     memset(w,0,sizeof(w));
 89     memset(v,0,sizeof(v));
 90     memset(vv,0,sizeof(vv));
 91 }
 92 bool cmp(struct query aa,struct query bb)
 93 {
 94     if(pos[aa.id]<pos[bb.id])
 95         return true;
 96     if(pos[aa.id]==pos[bb.id])
 97     {
 98         if(aa.r<bb.r)
 99             return true;
100     }
101     return false;
102 }
103 void ad(int value)
104 {
105     if(sum[value]==k)
106         ans--;
107     sum[value]++;
108     if(sum[value]==k)
109        ans++;
110 }
111 void del(int value)
112 {
113     if(sum[value]==k)
114         ans--;
115     sum[value]--;
116     if(sum[value]==k)
117         ans++;
118 }
119 int main()
120 {
121     scanf("%d",&T);
122     for(int i=1;i<=T;i++)
123     {
124         init();
125         scanf("%d %d",&n,&k);
126         int block=sqrt(n);
127         for(int j=1;j<=n;j++){
128             scanf("%d",&w[j]);
129             v[j]=w[j];
130             }
131             sort(w+1,w+1+n);
132         for(int j=1;j<=n;j++){
133             v[j]=lower_bound(w+1,w+n+1,v[j])-w-1;
134             }
135         for(int j=1;j<n;j++){
136             scanf("%d %d",&x,&y);
137             add(x,y);add(y,x);
138         }
139         getdfs(1,1);
140         for(int j=1;j<=n;j++)
141             vv[in[j]]=v[j];// 将树上的权值 下放到区间当中
142         scanf("%d",&q);
143         int exm;
144         for(int j=1;j<=q;j++){
145             scanf("%d",&exm);
146             M[j].l=in[exm];
147             M[j].r=out[exm];
148             M[j].id=j;
149             pos[j]=(M[j].l)/block;//分块 处理的不是特别好
150         }
151         printf("Case #%d:
",i);
152         sort(M+1,M+1+q,cmp);
153         int l=1, r=0;//初始区间
154         ad(vv[++r]);
155         for(int j=1; j<=q; j++)
156         {
157             while(r<M[j].r) ad(vv[++r]);
158             while(r>M[j].r) del(vv[r--]);
159             while(l<M[j].l) del(vv[l++]);
160             while(l>M[j].l) ad(vv[--l]);
161             re[M[j].id]=ans;
162         }
163         for(int j=1;j<=q;j++)
164             printf("%d
",re[j]);
165         if(i!=T)
166             printf("
");
167     }
168     return 0;
169 }