三部曲（内部试题）

建议同学们先做题再看答案      

【问题描述】 

因为外来的入侵，国王决定在某些城市加派士兵。所有城市初始士兵数量为0。当城市i被加派了k名士兵时。城市i的所有子城市需要被加派k+1名士兵。这些子城市的所有子城市需要被加派k+2名士兵。以此类推。当然，加派士兵的同时，国王也需要不断了解当前的情况。于是他随时可能询问以城市i为根的子树中的所有城市共被加派了多少士兵。 你现在是国王的军事大臣，你能回答出国王的每个询问么？ 

【输入格式】 

第一行，包含两个整数N,P代表城市数量以及国王的命令的数量。 第二行N-1个整数，表示2-N号每个节点的父亲节点。 接下来的P行，每行代表国王的一个命令，命令分两种: A X K 在城市X加入K个士兵 Q X 询问以城市X为根的子树中所有士兵数量的和。 

【输出格式】 

对于每个Q，输出答案。 

【样例输入】

 【样例输出】

【数据规模与约定】 

对于50%的数据，1≤N≤1000 1≤P≤300。 对于100%的数据，1≤N≤50000 1≤P≤100000 1≤X≤N 0≤K≤1000。

题解出自清北NOIP训练营学员，详情见：https://i-jvxie.com/archives/67.htm

l题目还算是好理解的，然而看看数据范围，朴素的 dfs 只能拿前 50 分
所以我们要相处一点高效的方法，比如 log 级别的时间复杂度，那么很容易就能联想到线段树
看样子是很难做线段树，因为这是个树结构的图而非线性结构
但是！！有种神奇的方式可以将树结构转化为线性结构————dfs 序

题解：dfs 预处理 + 线段树

dfs 一趟可以处理出每个点的 dfs 序，也可以知道这个点下还有多少个节点
那么我们就可以得出从每个点开始的区间为哪一个，再借助线段树就可以轻松做到区间求和 / 修改等操作了
但是还有个问题————节点往下要每次加上 1，该如何解决呢？
其实我们可以在处理 dfs 序时顺便处理出若根节点（1）加 0 时，每个节点会加多少，这里设为 h
然后用线段树求出每个区间 h 的和，以便之后的另一棵线段树使用
然后每次在 A 操作的时候，将要加的 k 值减去这个节点的 h，在区间修改的时候加上区间的 h 和
那么就相当于我们做完了节点加数的递增操作

时间复杂度

大概的时间复杂度可以这么计算：
dfs 预处理 O(n)+ 线段树建树 O(n)+ 线段树操作总数 (plogn)=O(2n+plogn)
还是远远小于 1s 的~
至此，我们也就得出了一个正解，下面放上完整代码

C++

1

#include

#include

#include

#include

#define N 100010

#define ll long long

#define fmid (l+r)>>1 

#define lson l,mid,p<<1

#define rson mid+1,r,(p<<1)+1 

struct edge{

    int to,go;

}road[N];

//tree为要求的和，tree_h为树层和 

struct Tree{

    int l,r,eps;

    ll tot,h;

}tree[N<<2],tree_h[N<<2];

int len,dfs_order[N],dfs_son[N],dfs_dev[N],head[N],ch[N];

bool vis_dfs[N];

//边表处理 

void add(int a,int b){

    ++len;

    road[len].to=b;

    road[len].go=head[a];

    head[a]=len;

    return ;

}

//dfs预处理 

void dfs(int a,int dev){

    int i=head[a],b,ret=0;

    ++len;

    dfs_order[a]=len;

    vis_dfs[a]=1;

    dfs_dev[len]=dev;

    while(i!=-1){

        b=road[i].to;

        dfs(b,dev+1);

        ret+=dfs_son[b]+1;

        i=road[i].go;

    }

    dfs_son[a]=ret;

    return ;

}

//建树 

void build(int l,int r,int p){

    if(l==r){

        tree_h[p].tot=dfs_dev[l];

        tree_h[p].l=tree_h[p].r=l;

        tree[p].l=tree[p].r=r;

        return ;

    }

    int mid=(l+r)>>1;

    build(lson);build(rson);

    tree_h[p].l=tree[p].l=l;

    tree_h[p].r=tree[p].r=r;

    tree_h[p].tot=tree_h[p<<1].tot+tree_h[(p<<1)+1].tot;

    return ;

}

//区间修改 

void push_down(int p){

    if(tree[p].eps){

        tree[p<<1].h+=tree[p].h,tree[p<<1].eps+=tree[p].eps;

        tree[(p<<1)+1].h+=tree[p].h,tree[(p<<1)+1].eps+=tree[p].eps;

        int mid=(tree[p].l+tree[p].r)>>1;

        tree[p<<1].tot+=tree[p].h*(mid-tree[p].l+1)+tree[p].eps*tree_h[p<<1].tot;

        tree[(p<<1)+1].tot+=tree[p].h*(tree[p].r-mid)+tree[p].eps*tree_h[(p<<1)+1].tot;

        tree[p].eps=0,tree[p].h=0;

    }

    return ;

}

void update(int kl,int kr,int p,int k){

    int l=tree[p].l,r=tree[p].r;

    if(l>=kl && kr>=r){

        tree[p].h+=k;

        tree[p].eps++;

        tree[p].tot+=tree_h[p].tot+(r-l+1)*k;

        return ;

    }

    push_down(p);

    int mid=fmid;

    if(kl<=mid) update(kl,kr,p<<1,k);

    if(kr>mid) update(kl,kr,(p<<1)+1,k);

    tree[p].tot=tree[p<<1].tot+tree[(p<<1)+1].tot;

    return ;

}

//区间查询 

ll query(int kl,int kr,int p){

    int l=tree[p].l,r=tree[p].r;

    if(l>=kl && kr>=r) return tree[p].tot;

    push_down(p);

    int mid=fmid;

    if(kl<=mid){

        if(mid<<1)+query(kl,kr,(p<<1)+1);<="" p="">

        else return query(kl,kr,p<<1);

    }

    else return query(kl,kr,(p<<1)+1);

}

int main(){

//  freopen("truetears.in","r",stdin);

//  freopen("truetears.out","w",stdout);

    memset(head,-1,sizeof(head));

    int n,p,i,a,b;

    char s[5];

    scanf("%d%d",&n,&p);

    for(i=2;i<=n;i++){

        scanf("%d",&a);

        add(a,i);

    }

    len=0;

    for(i=1;i<=n;i++)

        if(!vis_dfs[i])

            dfs(i,0);

    build(1,n,1);

    while(p--){

        scanf("%s",s);

        switch(s[0]){

            case 'A':{

                scanf("%d%d",&a,&b);

                b-=dfs_dev[dfs_order[a]]; 

                printf("b = %dn",b);

                update(dfs_order[a],dfs_order[a]+dfs_son[a],1,b);

                break ;

            }

            case 'Q':{

                scanf("%d",&a);

                printf("%lldn",query(dfs_order[a],dfs_order[a]+dfs_son[a],1));

                break ;

            }

        }

    }

    return 0;

}

END

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com