[ACM-ICPC 2018 Shenyang Network preliminaries] J. Ka Chang (block + DFS sequence)

Topic link

The question ：

Given a tree $n$ A dot tree , There are two operations ：
$1.$ Give all depths to $L$ Add the point weight of $X$.
$2.$ Query root is $X$ The point weight sum of the subtree of .
give $q$ operations , For each operation $2$, Output results .
$(1\le n,q\le 10^5)$

Ideas ：

If only the operation $1$, We can maintain $bfs$ order , In this way, the points with the same depth must be in a continuous interval .
If only the operation $2$, We can maintain $dfs$ order , In this way, the subtree of a point must be in a continuous interval .
But you can't have both , We can only keep one of them .

For this operation $2$, We still maintain a $dfs$ order , It becomes interval summation .

Now the main problem is to solve the operation $1$.
We can find out , The point weights of points at the same depth must be the same . So we need to get the weight sum of a subtree , We only need to know the number of points in each depth of the subtree . But when we calculate , Cannot traverse all depths , We can't preprocess the number of all depth points of its subtree for each point . Then there is the following practice .

We classify all points by depth , Put together at the same depth .
consider Block according to the size of the classified set .

When the set size of a certain depth $\le \sqrt{n}$ when , So when we want to update the depth , Direct violence $+$ Single point modification , The complexity is $o(n\sqrt{n}logn)$.
When the set size of a certain depth $\ge \sqrt{n}$ when , The number of such collections must be less than $\sqrt{n}$, We can for each point ,
Preprocessing shows that this is less than $\sqrt{n}$ The size of a set in a subtree , And then when you check , Violence traverses these depths , Get the number directly to calculate .

such , The total complexity is $o(n\sqrt{n}logn)$.

Code

ps: The depth of the question is from $0$ At the beginning ...

#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;
}