题意:给你一棵有$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]);
}