三部曲（内部试题） 建议同学们先做题再看答案       【问题描述】  因为外来的入侵，国王决定在某些城市加派士兵。所有城市初始士兵数量为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