cdoj 574 High-level ancients dfs序+线段树 每个点所加权值不同
High-level ancients
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.uestc.edu.cn/#/problem/show/574
Description
Love8909 is keen on the history of Kingdom ACM. He admires the heroic undertakings of Lxhgww and Haibo. Inspired by those sagas, Love8909 picked up his courage and tried to build up his own kingdom. He named it as A230.
After hard working for several years, Love8909 is about to fulfill his dream. However, there is still one thing to do: setting up the defense network. As Kingdom EDC looks at territory and people of A230 fiercely as a tiger does, Love8909 has to make it as soon as possible.
The defense network Love8909 wants to use is the same as the one used by Lxhgww and Haibo. He also connects all cities with roads which form a tree structure, and the capital city is City 1, which is the root of this tree. Love8909 sends commands to inform cities to add soldiers. The command, being same to those of the ancients, with two values, X and K, means sending K soldiers to City X, sending K+1 soldiers to sons of City X, sending K+2 soldiers to sons of sons of City X and so on. Initially there are no soldiers in any city.
Love8909 may adjust the arrangement of soldiers ever and again. He asks questions about how many soldiers in the subtree rooted at City X. A subtree rooted at City X includes City X itself and all of its descendants. As Love8909's military counselor, you are responsible to complete all his commands and answer his questions.
Input
The first line of the input will be an integer T (T≤20) indicating the number of cases.
For each case, the first line contains two integers: N P, representing the number of cities in A230 and number of operations given by love8909.
The next line lists N−1 integers, in which the ith number, denoted as Xi+1, represents there is a road from City Xi+1 to City i+1. Note that the City 1has been omitted. 1≤Xi+1≤N for 2≤i≤N.
Then P lines follow, each gives an operation. Each operation belongs to either kind:
A X K. An adding-soldier command.Q X. A question about how many soldiers in the subtree rooted at City X.
We guarantee that the cities form a rooted tree and the root is at City 1, which is the capital.
1≤N≤50000, 1≤P≤100000, 1≤X≤N, 0≤K≤1000.
Output
For each case, print Case #k: first in a single line, in which k represents the case number which starts from 1. Then for each Query X operation, print the answer in a single line.
Sample Input
1
7 10
1 1 2 2 5 5
Q 1
A 2 1
Q 1
Q 2
Q 5
A 5 0
Q 5
A 3 1
Q 1
Q 2
Sample Output
Case #1:
0
11
11
8
10
14
13
HINT
题意
给你一棵以1为根的树，有两个操作
1.A x k，让x增加k，x的儿子增加k+1，x的孙子增加k+2....x的t代儿子增加k+t
2.Q x , 查询x的子树的权值和是多少
题解：
处理子树的问题，我们一般会想到用dfs序将其转换成一段连续的区间。
子树中每个点所加的值和深度有关。我们用dp[x]表示x的深度，那么x的子树＋val，对于x子树某节点i权值＋d[i]-dp[x]+val。
这样可以把更新操作改成两部分
１．这个区间＋val-dp[x]
２．每个点＋dp[i]
关键在于如何处理第二个问题。其实不难，我们可以建一颗线段树，线段树每个节点加一个dpsum[x]记录这个区间的深度和，再加一个c[x]记录这个区间被更新过多少次。其余的和普通线段树没什么区别了。
那么权值和＝\(sum[ls]+sum[rs]+dpsum[x]*c[x]+lazy[x]*len\)。
sum[ls]表示左半区间的和，sum[rs]表示右半区间的和，lazy[x]表示对于整个区间所加值，len表示区间长度。
更深层次地剖析：
我把这类问题抽象一下，就是给一个区间[l,r]，再给一个数k,每个点的权值＋a[i]*k(l<=i<=r)，然后支持区间求和,想想是不是。
这个方法非常有用，对于区间加上等差数列也很适用。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100050
ll n,m,cas=0;
ll tot,last[N];
ll cnt,Size[N],dp[N],rk[N],kth[N];
struct Tree{ll l,r,j,c,sum,dpsum;}tr[N<<2];
struct Edge{ll from,to,s;}edges[N<<1];
template<typename T>void read(T&x)
{
ll k=0; char c=getchar();
x=0;
while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
if (c==EOF)exit(0);
while(isdigit(c))x=x*10+c-'0',c=getchar();
x=k?-x:x;
}
void read_char(char &c)
{while(!isalpha(c=getchar())&&c!=EOF);}
void AddEdge(ll x,ll y)
{
edges[++tot]=Edge{x,y,last[x]};
last[x]=tot;
}
void dfs(ll x,ll pre)
{
rk[x]=++cnt;
kth[cnt]=x;
Size[x]=1;
dp[x]=dp[pre]+1;
for(ll i=last[x];i;i=edges[i].s)
{
Edge &e=edges[i];
if (e.to==pre)continue;
dfs(e.to,x);
Size[x]+=Size[e.to];
}
}
void push_up(ll x)
{
ll len=tr[x].r-tr[x].l+1;
tr[x].sum=tr[x].j*len;
tr[x].sum+=tr[x].c*tr[x].dpsum;
if (len==1)return ;
tr[x].sum+=tr[x<<1].sum+tr[x<<1|1].sum;
}
void push_down(ll x)
{
Tree &a=tr[x<<1],&b=tr[x<<1|1];
a.j+=tr[x].j;
b.j+=tr[x].j;
a.c+=tr[x].c;
b.c+=tr[x].c;
push_up(x<<1);
push_up(x<<1|1);
tr[x].j=0;
tr[x].c=0;
}
void bt(ll x,ll l,ll r)
{
tr[x].l=l; tr[x].r=r; tr[x].j=0; tr[x].c=0; tr[x].sum=0;
if (l==r)
{
tr[x].dpsum=dp[kth[l]];
return;
}
ll mid=(l+r)>>1;
bt(x<<1,l,mid);
bt(x<<1|1,mid+1,r);
tr[x].dpsum=tr[x<<1].dpsum+tr[x<<1|1].dpsum;
}
void update(ll x,ll l,ll r,ll tt)
{
if (l<=tr[x].l&&tr[x].r<=r)
{
tr[x].j+=tt;
tr[x].c++;
push_up(x);
return ;
}
ll mid=(tr[x].l+tr[x].r)>>1;
push_down(x);
if (l<=mid)update(x<<1,l,r,tt);
if (mid<r)update(x<<1|1,l,r,tt);
push_up(x);
}
ll query(ll x,ll l,ll r)
{
if(l<=tr[x].l&&tr[x].r<=r)
return tr[x].sum;
ll mid=(tr[x].l+tr[x].r)>>1,ans=0;
push_down(x);
if (l<=mid)ans=query(x<<1,l,r);
if (mid<r)ans+=query(x<<1|1,l,r);
push_up(x);
return ans;
}
void work()
{
printf("Case #%lld:\n",++cas);
read(n); read(m);
for(ll i=2;i<=n;i++)
{
ll x;
read(x);
AddEdge(i,x);
AddEdge(x,i);
}
dfs(1,0);
bt(1,1,n);
for(ll i=1;i<=m;i++)
{
char id; ll x,tt;
read_char(id); read(x);
if (id=='Q')
{
printf("%lld\n",query(1,rk[x],rk[x]+Size[x]-1));
}
if (id=='A')
{
read(tt);
update(1,rk[x],rk[x]+Size[x]-1,tt-dp[x]);
}
}
}
void clear()
{
cnt=0; tot=0;
memset(last,0,sizeof(last));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("aa.in","r",stdin);
#endif
ll q;
read(q);
while(q--)
{
clear();
work();
}
}
最新文章
- 【Java每日一题】20161220
- mysql 安装以及运行
- NOIP2014 总结
- pfile 与 spfile
- 第十章实践——系统级I/O代码运行
- nodeschool.io 10
- POJ-2752 Seek the Name, Seek the Fame（KMP，前缀与后缀相等）
- C# 判断是否为闰年的条件各是
- Linux 日常使用指令大全
- 大型项目使用Automake/Autoconf完成编译配置
- CSS盒模型和定位的类型
- C#第六天
- Mac下eclipse导入其他工程中文注释出现乱码解决方案
- Spring Boot使用Druid连接池基本配置
- pyqt4
- Jquery常用开发插件收集
- 【Unity笔记】碰撞器（Collision）与触发器（Trigger）的区别
- 蚂蚁社招Java-第四轮电话面试【技术终面】
- Wiki版产品需求---产品需求文档到底是谁的？产品到底是谁的？
- 跟着百度学PHP[14]-PDO的预处理语句1