zcmimi's blog
avatar
zc
2020-10-07 20:03:39
  • 本文总阅读量

查看原题

点击跳转

题意:

n个节点的树,有r种属性,每个点属于一种属性.有q次询问,每次询问给r_1,r_2,问有多少对点(e_1, e_2)满足e_1属性为 r_1,e_2属性为r_2,且e_1e_2的祖先. (n,q \le 2 \times 10^5, r \le 25000,时限5s)

首先将询问离线

不管枚举e_1统计子树中e_2的数量

还是枚举e_2统计到根节点路径上e_1的数量

都是\mathcal O(nr)

可以考虑将两种方法结合,使用根号分治

r_2的总数目为S

S\ge \sqrt n,枚举e_2,统计e_1(不超过\sqrt n个),复杂度\mathcal O(q\sqrt n)

否则枚举e_1,统计e_2(子树中的r_2不会超过\sqrt n个),复杂度\mathcal O(n\sqrt n)

具体看代码

#include<bits/stdc++.h>
int rd(){int x=0;char c;bool f=0;for(c=getchar();c<'0'||'9'<c;c=getchar())f^=c=='-';for(x=c-48,c=getchar();'0'<=c&&c<='9';x=x*10+c-48,c=getchar());return f?-x:x;}
const int N=200011;
int n,r,q,a[N],s[N],ans[N],cnt[30300];
using namespace std;
vector<int>e[N];
#define mp make_pair
#define pr pair<int,int>
vector<pr>r1[N],r2[N];
map<pr,int>T;
void dfs(int x){ // 统计子树中r2
    for(pr i:r1[a[x]])ans[i.first]-=cnt[i.second];// 不超过sqr个
    ++cnt[a[x]];
    for(int to:e[x])dfs(to);
    for(pr i:r1[a[x]])ans[i.first]+=cnt[i.second];
}
void DFS(int x){
    ++cnt[a[x]];
    for(pr i:r2[a[x]])ans[i.first]+=cnt[i.second];// 不超过sqr个
    for(int to:e[x])DFS(to);
    --cnt[a[x]];
}
int main(){
    n=rd(),r=rd(),q=rd();
    int x,y,sqr=sqrt(n);
    ++s[a[1]=rd()];
    for(int i=2;i<=n;++i)
        e[x=rd()].push_back(i),
        ++s[a[i]=rd()];
    for(int i=1;i<=q;++i){
        x=rd(),y=rd();
        if(T[mp(x,y)]){ans[i]=-T[mp(x,y)];continue;}
        else T[mp(x,y)]=i;
        if(s[y]<sqr)r2[y].push_back(mp(i,x));
        else r1[x].push_back(std::mp(i,y));
    }
    dfs(1);memset(cnt,0,sizeof cnt);DFS(1);
    for(int i=1;i<=q;++i)
        printf("%d\n",ans[ans[i]<0?-ans[i]:i]);
}
LG 5901 [IOI2009]regions
comment评论
Search
search