题意:给你一棵有$n$个节点的树,每个节点有点权$val$,求每个点子树点权众数之和
$n\le10^5 $
分析:
由于不带修改,$n$范围相对较小,不难想到将子树转化为DFS序用莫队解决
每一次$DFS$到点$u$时,对应的询问的左端点即为当前DFS序,在以$u$为根的$DFS$递归结束后,右端点即为结束后的DFS序
因此不难写出以下代码
struct Query{ int l,r,id; bool operator <(const Query &x)const{ if (l/len!=x.l/len) return l/len<x.l/len; return r/len<x.r/len; //len为块长 } }q[MAXN]; void dfs(int u,int fa){ dfn[u]=++dcnt; q[dcnt].id=u; q[dcnt].l=dcnt; col[dcnt]=a[u]; for (int i=head[u];i;i=E[i].nxt){ int v=E[i].to; if (v==fa) continue; dfs(v,u); } q[dfn[u]].r=dcnt; }
然后即可在DFS序上跑莫队,每一次用数据结构维护出现的次数以及该出现次数的权值和,答案即为出现次数为众数出现次数的权值之和
//bucket[x]为x出现次数,insert为Data-Structure的插入操作,qmax是在Data-Structure中询问众数之和 void add(int x){//等价与撤销对原来出现次数的贡献,改为对原来出现次数+1的贡献 int now=col[x]; if (bucket[now]) insert(bucket[now],-now); bucket[now]++; insert(bucket[now],now); } void del(int x){//同上 int now=col[x]; insert(bucket[now],-now); bucket[now]--; if (bucket[now]) insert(bucket[now],now); } void solve(){ sort(q+1,q+1+n); int l=1,r=0; for (int i=1;i<=n;i++){ while(l<q[i].l) del(l++); while(r<q[i].r) add(++r); while(q[i].l<l) add(--l); while(q[i].r<r) del(r--); ans[q[i].id]=query(); } }
每一次$l,r$指针的移动,时间复杂度都为$O(Data-Structure)$,因此该算法时间复杂度为$O(n\times \sqrt{n} \times insert+n\times query)$
因此若用权值线段树,$set$等树形结构,时间复杂度为$O(n\times\sqrt{n}\times\log{n}$)
优化
因为以上数据结构都为树形,每次$insert$都要将信息上推到根节点
当修改与询问时间平衡,即$n\times \sqrt{n} \times insert=n\times query$时算法效率最高
因此考虑$O(1)$修改,$O(\sqrt{n})$内询问的数据结构
因为分块单点修改复杂度为$O(1)$,不难想到对权值的出现次数进行分块
类比权值线段树与权值树状数组,不难写出以下代码
#define ll long long const int MAXN=1e5+5; const int MAXM=350; int len,block,L[MAXM],R[MAXM],belong[MAXN]; ll val[MAXN],num[MAXM]; //L[]每块左端点下标,R[]每块右端点下标,belong[x]权值出现次数为x时属于那一块 //val[x]出现次数为x的权值之和,num[x]表示落在[L[x],R[x]]所有权值和 void insert(int v,int x){//每次插入只对当前单点和所处块有贡献 val[v]+=x;num[belong[v]]+=x; } ll query(){//找到众数和 for (int i=block;i;i--){//遍历每一块 if (num[i]){//如果这个块中有数出现过,因为之前没有return,所以众数一定在这一块中 for (int j=R[i];j>=L[i];j--){ if (val[j]) return val[j];//找到众数,返回其权值和 } } } }
这样,我们就做到了$O(1)$修改,$O(\sqrt{n})$询问
整个算法时间复杂度为$O(n\times\sqrt{n})$
这种$O(1)$插入的分块$trick$ 也叫作值域分块
AC Code
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cctype> using namespace std; const int MAXN=1e5+5; const int MAXM=350; struct Edge{ int to,nxt; }E[MAXN<<1]; int head[MAXN],cnt; void add(int x,int y){ E[++cnt].to=y; E[cnt].nxt=head[x]; head[x]=cnt; } int n,a[MAXN],x,y; #define ll long long int len,block,L[MAXM],R[MAXM],belong[MAXN],dfn[MAXN],dcnt,bucket[MAXN]; ll val[MAXN],num[MAXM],col[MAXN]; ll ans[MAXN]; struct Query{ int l,r,id; bool operator <(const Query &x)const{ if (l/len!=x.l/len) return l/len<x.l/len; return r/len<x.r/len; } }q[MAXN]; void dfs(int u,int fa){ dfn[u]=++dcnt; q[dcnt].id=u; q[dcnt].l=dcnt; col[dcnt]=a[u]; for (int i=head[u];i;i=E[i].nxt){ int v=E[i].to; if (v==fa) continue; dfs(v,u); } q[dfn[u]].r=dcnt; } void insert(int v,int x){ val[v]+=x;num[belong[v]]+=x; } ll query(){ for (int i=block;i;i--){ if (num[i]){ for (int j=R[i];j>=L[i];j--){ if (val[j]) return val[j]; } } } } void add(int x){ int now=col[x]; if (bucket[now]) insert(bucket[now],-now); bucket[now]++; insert(bucket[now],now); } void del(int x){ int now=col[x]; insert(bucket[now],-now); bucket[now]--; if (bucket[now]) insert(bucket[now],now); } void solve(){ sort(q+1,q+1+n); int l=1,r=0; for (int i=1;i<=n;i++){ while(l<q[i].l) del(l++); while(r<q[i].r) add(++r); while(q[i].l<l) add(--l); while(q[i].r<r) del(r--); ans[q[i].id]=query(); } } int main(){ scanf("%d",&n); len=sqrt(n);block=n/len; if (block*len!=n) block++; for (int i=1;i<=block;i++){ L[i]=R[i-1]+1; R[i]=min(i*len,n); for (int j=L[i];j<=R[i];j++) belong[j]=i; } for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<n;i++){ scanf("%d %d",&x,&y); add(x,y);add(y,x); } dfs(1,1); solve(); for (int i=1;i<=n;i++) printf("%lld ",ans[i]); }