正文
hdu 4358 Boring counting dfs序+莫队+离散化
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
Boring counting
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 98304/98304 K (Java/Others)
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 5 , 1 <= K <= N )
Then come N integers in the second line, they are the weights of vertice 1 to N. ( 0 <= weight <= 10 9 )
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 5 )
For next Q lines, each with an integer u, as the root of the subtree described above.
For each test case, the first line contains two integers N and K, as described above. ( 1<= N <= 10 5 , 1 <= K <= N )
Then come N integers in the second line, they are the weights of vertice 1 to N. ( 0 <= weight <= 10 9 )
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 5 )
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
3 1
1 2 2
1 2
1 3
3
2
1
3
Sample Output
Case #1:
1
1
1
1
1
1
Author
fish@UESTC_Oblivion
Source
2012 Multi-University Training Contest 6
题意：给你一棵树，n个节点，以1为根，每个节点有一个权值w；
q个询问，每个询问问，以该点为根的子树下某个权值出现k次的个数；
思路：首先w很大，用map会超时；需要离散化一下；
处理子树问题，利用dfs序，改成区间处理；
区间处理权值出现k次的树，利用莫队得到答案；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
const int N=1e5+,M=1e6+,inf=1e9+;
const ll INF=1e18+,mod=;
struct is
{
int v,nex;
}edge[N<<];
int head[N<<],edg,in[N],out[N],tot,pos[N],w[N];
vector<int>l;
int a[N],flag[N];
void add(int u,int v)
{
edg++;
edge[edg].v=v;
edge[edg].nex=head[u];
head[u]=edg;
}
void dfs(int u,int fa)
{
in[u]=++tot;
for(int i=head[u];i!=-;i=edge[i].nex)
{
int v=edge[i].v;
if(v==fa)continue;
dfs(v,u);
}
out[u]=tot;
}
struct hh
{
int l,r,now;
bool operator <(const hh b)
{
if(pos[l]!=pos[b.l])
return pos[l]<pos[b.l];
return r<b.r;
}
}p[N];
int ans[N],mp[N],z[N];
void add(int pos)
{
z[mp[a[pos]]]--;
mp[a[pos]]++;
z[mp[a[pos]]]++;
}
void del(int pos)
{
z[mp[a[pos]]]--;
mp[a[pos]]--;
z[mp[a[pos]]]++;
}
void init(int n)
{
l.clear();
memset(mp,,sizeof(mp));
memset(z,,sizeof(z));
int s=(int)(sqrt(n));
for(int i=;i<=n;i++)
pos[i]=(i-)/s+;
memset(head,-,sizeof(head));
memset(a,,sizeof(a));
edg=;
tot=;
}
int main()
{
int T,cas=;
scanf("%d",&T);
while(T--)
{
if(cas!=)
printf("\n");
int n,k;
scanf("%d%d",&n,&k);
init(n);
for(int i=;i<=n;i++)
scanf("%d",&w[i]),l.push_back(w[i]);
sort(l.begin(),l.end());
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(,-);
for(int i=;i<=n;i++)
flag[in[i]]=i;
for(int i=;i<=n;i++)
a[i]=lower_bound(l.begin(),l.end(),w[flag[i]])-l.begin();
int q;
scanf("%d",&q);
for(int i=;i<=q;i++)
{
int x;
scanf("%d",&x);
p[i].l=in[x];
p[i].r=out[x];
p[i].now=i;
}
sort(p+,p++q);
int L=,R=;
for(int i=;i<=q;i++)
{
//cout<<p[i].l<<" "<<p[i].r<<" "<<p[i].now<<endl;
while(L<p[i].l)
{
del(L);
L++;
}
while(L>p[i].l)
{
L--;
add(L);
}
while(R>p[i].r)
{
del(R);
R--;
}
while(R<p[i].r)
{
R++;
add(R);
}
ans[p[i].now]=z[k];
}
printf("Case #%d:\n",cas++);
for(int i=;i<=q;i++)
printf("%d\n",ans[i]);
}
return ;
}
