Boring counting

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

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

Sample Output

Case #1:
1
1
1

题意：有一棵树，每个点有一个权值，m次询问，问这个点的子树里权值出现 k 次的权值个数

思路：

一棵树，每次对询问的节点去遍历它的儿子并计数的话 10^5次询问，每次询问根节点，那时间百分之百的不够了

对于子树问题的，我们都可以打出一个dfs序把它转化为区间问题，这题也不例外，打了dfs序之后就成了区间问题了

然后使用莫队就妥妥地搞定，但是注意题目给的权值是到了 10^9,而并没有那么多节点，而且你开不了10^9数组去记录该值出现的次数。所以要离散化处理。离散化处理的方法有两种，一种是用map，但是这种会耗时间一点，另一种就是去打个离散化，重新给它赋值，因为节点数不超过10^5，所以打个10^5数组存就可以了。

注意：我们在把树进行dfs序操作之后，对于每个点它的左标签不一定是等于他原本的下标的，所以如果还按照原本的权值去操作的话就搓了。

比如这组数据：

5 2

1 1 2 10 10

1 3

1 2

2 4

2 5

1 2 3 4 5

这个树打了dfs序之后 4 这个点的左标签右标签分别是 3，所以这时候就不能直接传 val [ x ] 了，要做一个操作

在打 dfs序的过程中拿一个数组 val2[] 去存新的权值 val2[tm] = val1[now]

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
#define maxn 100005

int n,m,k,tm,Ans;
struct trie{
int l,r;
}tree[maxn];
map<int,int>mp;
int val1[maxn],val2[maxn];
vector<int>G[maxn];
struct question{
int l,r,id,pos;
}q[maxn]; 
bool cmp(question a,question b){
if(a.pos != b.pos){
return a.pos < b.pos;
}
return a.r < b.r;
}
void dfs(int now,int pre){
tree[now].l = ++tm;
val2[tm] = val1[now];  // 做了dfs序之后，对应下标的值要重新赋 
int len = G[now].size();
for(int i = 0;i < len;i++){
if(G[now][i] != pre)
dfs(G[now][i],now);
}
tree[now].r = tm;
return ;
}
int ans[maxn],flag[maxn];
void add(int x){
if(flag[x] == k)
Ans--;
flag[x]++;
if(flag[x] == k)
Ans++;
}
void dele(int x){
if(flag[x] == k) 
Ans--;
flag[x]--;
if(flag[x] == k) 
Ans++;
}
int main(){
int T,Case = 1,u,v,cnt,x;
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&k);
cnt = 0;
mp.clear();
for(int i = 1;i <= n;i++){
scanf("%d",&x); 
if(!mp.count(x))// 离散化赋值 
mp[x] = ++cnt;
val1[i] = mp[x];
}
for(int i = 1;i <= n;i++){
G[i].clear();
}
for(int i = 1;i < n;i++){
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
tm = 0;
dfs(1,-1);// 打dfs序 
scanf("%d",&m);
int block = sqrt(n);
for(int i = 1;i <= m;i++){
scanf("%d",&u);
q[i].l = tree[u].l;//把询问做 dfs序赋值 
q[i].r = tree[u].r;
q[i].pos = tree[u].l / block; //分块 
q[i].id = i;
}
sort(q + 1,q + 1 + m,cmp);//分块排序 
mem(flag,0);
int l = 1,r = 0;
Ans = 0;
for(int i = 1;i <= m;i++){
while(r < q[i].r)
add(val2[++r]);
while(r > q[i].r)
dele(val2[r--]);
while(l < q[i].l)
dele(val2[l++]);
while(l > q[i].l)
add(val2[--l]);
ans[q[i].id] = Ans;
}
printf("Case #%d:\n",Case++);
for(int i = 1;i <= m;i++)
printf("%d\n",ans[i]);
if(T != 0)
puts("");
}
return 0;
}

秒客网

莫队 + dfs序 + 离散化处理 HDU 4358

Boring counting

相关文章