[ACM-ICPC 2018 沈阳赛区网络预赛] J.Ka Chang （分块+dfs序）

题目链接

题意：

给定一棵$n$个点的树，有两种操作：
$1.$给所有深度为$L$的点权值加上$X$。
$2.$查询根为$X$的子树的点权和。
给出$q$次操作，对于每次操作$2$，输出结果。
$(1\le n,q\le 10^5)$

思路：

如果只有操作$1$，我们可以维护$bfs$序，这样同深度的点一定在一段连续的区间中。
如果只有操作$2$，我们可以维护$dfs$序，这样某个点的子树一定在一段连续的区间中。
但是二者不可兼得，我们只能保留其一。

对于这题操作$2$，我们仍维护一个$dfs$序，就变成区间求和了。

现在主要的问题是解决操作$1$。
我们可以发现，同一深度点的点权一定是相同的。 所以要得到某个子树的权值和，我们只要知道这个子树每个深度的点的个数即可。但是我们计算的时候，不能遍历所有深度，我们也没法对于每个点预处理它的子树所有的深度点的个数。然后就有了后面的做法。

我们把所有的点按深度归类，同一个深度的放在一起。
考虑按归类后的集合大小分块。

当某个深度的集合大小 $\le \sqrt{n}$时，那么我们要更新该深度的时候，直接暴力遍历$+$单点修改即可，复杂度为$o(n\sqrt{n}logn)$。
当某个深度的集合大小 $\ge \sqrt{n}$时，这样的集合数量肯定少于$\sqrt{n}$，我们可以对于每个点，
预处理出这不到$\sqrt{n}$个集合中在子树里的大小，然后查询的时候，暴力遍历这些深度，直接得到个数来计算。

这样，总的复杂度就是$o(n\sqrt{n}logn)$。

代码

ps:题中的深度是从$0$开始的。。。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod=1000000007;

const int N = 100001;
ll c[100005];
void add(int x,ll k) {
    
    while(x<=N) {
    
        c[x]+=k;
        x+=x&-x;
    }
}
ll getSum(int x) {
    
    ll res=0;
    while(x>0) {
    
        res+=c[x];
        x-=x&-x;
    } return res;
}

int n,B;
vector<int>v[100005];
vector<int>st[100005];
ll dval[100005];
int dep[100005],id[100005],idx,ed[100005],edd;
void dfs(int x,int pre)
{
    
    id[x]=++idx;
    edd=x;
    dep[x]=dep[pre]+1;
    for(int i=0;i<v[x].size();i++)
    {
    
        int to=v[x][i];
        if(to!=pre)
        {
    
            dfs(to,x);
        }
    }
    ed[x]=edd;
}
vector<int>dv[100005],g;
void dfs2(int x,int pre)
{
    
    for(int i=0;i<v[x].size();i++)
    {
    
        int to=v[x][i];
        if(to!=pre)
        {
    
            dfs2(to,x);
            for(int j=0;j<g.size();j++)dv[x][j]+=dv[to][j];
        }
    }
    for(int j=0;j<g.size();j++)if(g[j]==dep[x])dv[x][j]++;
}

int main()
{
    
    int q;
    scanf("%d%d",&n,&q);
    B=sqrt(n);
    for(int i=1;i<n;i++)
    {
    
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)st[dep[i]].push_back(i);
    for(int i=1;i<=n;i++)if(st[i].size()>B)g.push_back(i);
    for(int i=1;i<=n;i++)
    {
    
        for(int j=0;j<g.size();j++)dv[i].push_back(0);
    }
    dfs2(1,0);
    while(q--)
    {
    
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
    
            int d,x;
            scanf("%d%d",&d,&x);
            d++;
            if(st[d].size()<=B)
            {
    
                for(auto t:st[d])add(id[t],x);
            }
            else
            {
    
                dval[d]+=x;
            }
        }
        else
        {
    
            int x;
            scanf("%d",&x);
            ll ans=getSum(id[ed[x]])-getSum(id[x]-1);
            for(int j=0;j<g.size();j++)ans+=dv[x][j]*dval[g[j]];
            printf("%lld\n",ans);
        }
    }
    return 0;
}