三部曲(内部试题) 建议同学们先做题再看答案 【问题描述】 因为外来的入侵,国王决定在某些城市加派士兵。所有城市初始士兵数量为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:///archives/67.htm l题目还算是好理解的,然而看看数据范围,朴素的 dfs 只能拿前 50 分 dfs 一趟可以处理出每个点的 dfs 序,也可以知道这个点下还有多少个节点 大概的时间复杂度可以这么计算: C++ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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<kr) return query(kl,kr,p<<1)+query(kl,kr,(p<<1)+1); 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 = %d\n',b); update(dfs_order[a],dfs_order[a]+dfs_son[a],1,b); break ; } case 'Q':{ scanf('%d',&a); printf('%lld\n',query(dfs_order[a],dfs_order[a]+dfs_son[a],1)); break ; } } } return 0; |
|