cdoj 574 High-level ancients dfs序+线段树

时间:2022-10-15 00:08:43

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.

cdoj 574 High-level ancients dfs序+线段树

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序

dfs离散之后,维护线段树区间和,区间更新

我们很容易看出,他的更新是和deep有关的,deep越深的,更新越大

那么我们对于每个节点i,先区间更新y-deep[x],然后再使得更新一次,使得每个节点i增加deep[i]就好了

这样每个属于x的子树的都更新了 y - deep[x] + deep[i]

代码:

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
#define maxn 100010
struct Node
{
int l,r,d,val;
};
Node node[maxn];
vector<int>Q[maxn];
int TTT[maxn];
int cnt = ;
void dfs(int x,int fa,int d)
{
node[x].l = cnt;
node[x].d = d;
TTT[cnt]=x;
cnt++;
for(int i=;i<Q[x].size();i++)
{
int v = Q[x][i];
if(v==fa)continue;
dfs(v,x,d+);
}
node[x].r = cnt;
}
int d[maxn];
struct Seg
{
typedef long long SgTreeDataType;
struct treenode
{
int L , R ;
SgTreeDataType sum , lazy1 , lazy2;
}; treenode tree[maxn*]; inline void push_down(int o)
{
SgTreeDataType lazyval1 = tree[o].lazy1;
SgTreeDataType lazyval2 = tree[o].lazy2;
if(lazyval1==&&lazyval2==)return;
int L = tree[o].L , R = tree[o].R;
int mid = (L+R)/;
tree[*o].lazy1+=lazyval1;tree[*o].sum+=lazyval1*(mid-L+);
tree[*o+].lazy1+=lazyval1;tree[*o+].sum+=lazyval1*(R-mid); tree[*o].lazy2+=lazyval2;tree[*o].sum+=lazyval2*d[*o];
tree[*o+].lazy2+=lazyval2;tree[*o+].sum+=lazyval2*d[*o+];
tree[o].lazy1 = tree[o].lazy2 = ;
} inline void push_up(int o)
{
tree[o].sum = tree[*o].sum + tree[*o+].sum;
} inline void build_tree(int L , int R , int o)
{
tree[o].L = L , tree[o].R = R,tree[o].sum = tree[o].lazy1 = tree[o].lazy2 = ;
if(L==R)
d[o]=node[TTT[L]].d;
if (R > L)
{
int mid = (L+R) >> ;
build_tree(L,mid,o*);
build_tree(mid+,R,o*+);
d[o]=d[o*]+d[o*+];
}
} inline void updata1(int QL,int QR,SgTreeDataType v,int o)
{
int L = tree[o].L , R = tree[o].R;
if (QL <= L && R <= QR)
{
tree[o].lazy1 += v;
tree[o].sum += v * (R-L+);
}
else
{
push_down(o);
int mid = (L+R)>>;
if (QL <= mid) updata1(QL,QR,v,o*);
if (QR > mid) updata1(QL,QR,v,o*+);
push_up(o);
}
} inline void updata2(int QL,int QR,SgTreeDataType v,int o)
{
int L = tree[o].L , R = tree[o].R;
if (QL <= L && R <= QR)
{
tree[o].lazy2+=v;
tree[o].sum+=v*d[o];
}
else
{
push_down(o);
int mid = (L+R)>>;
if (QL <= mid) updata2(QL,QR,v,o*);
if (QR > mid) updata2(QL,QR,v,o*+);
push_up(o);
}
} inline SgTreeDataType query(int QL,int QR,int o)
{
int L = tree[o].L , R = tree[o].R;
if (QL <= L && R <= QR) return tree[o].sum;
else
{
push_down(o);
int mid = (L+R)>>;
SgTreeDataType res = ;
if (QL <= mid) res += query(QL,QR,*o);
if (QR > mid) res += query(QL,QR,*o+);
push_up(o);
return res;
}
}
}T; int main()
{
int t;scanf("%d",&t);
for(int cas=;cas<=t;cas++)
{
printf("Case #%d:\n",cas);
int n,q;
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)Q[i].clear(),node[i].val=;
cnt = ;
for(int i=;i<=n;i++)
{
int x,y;scanf("%d",&x);
y=i;
Q[x].push_back(y);
Q[y].push_back(x);
}
dfs(,-,);
T.build_tree(,n,);
string ch;
while(q--)
{
cin>>ch;
if(ch[]=='Q')
{
int x;scanf("%d",&x);
printf("%lld\n",T.query(node[x].l,node[x].r-,));
}
else
{
int x,y;scanf("%d%d",&x,&y);
T.updata1(node[x].l,node[x].r-,y-node[x].d,);
T.updata2(node[x].l,node[x].r-,,);
}
}
}
}

cdoj 574 High-level ancients dfs序+线段树的更多相关文章

  1. cdoj 574 High-level ancients dfs序&plus;线段树 每个点所加权值不同

    High-level ancients Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.uestc.edu.cn/#/problem/s ...

  2. Educational Codeforces Round 6 E dfs序&plus;线段树

    题意:给出一颗有根树的构造和一开始每个点的颜色 有两种操作 1 : 给定点的子树群体涂色 2 : 求给定点的子树中有多少种颜色 比较容易想到dfs序+线段树去做 dfs序是很久以前看的bilibili ...

  3. 【BZOJ-3252】攻略 DFS序 &plus; 线段树 &plus; 贪心

    3252: 攻略 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 339  Solved: 130[Submit][Status][Discuss] D ...

  4. Codeforces 343D Water Tree(DFS序 &plus; 线段树)

    题目大概说给一棵树,进行以下3个操作:把某结点为根的子树中各个结点值设为1.把某结点以及其各个祖先值设为0.询问某结点的值. 对于第一个操作就是经典的DFS序+线段树了.而对于第二个操作,考虑再维护一 ...

  5. BZOJ2434 &lbrack;Noi2011&rsqb;阿狸的打字机(AC自动机 &plus; fail树 &plus; DFS序 &plus; 线段树)

    题目这么说的: 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机.打字机上只有28个按键,分别印有26个小写英文字母和'B'.'P'两个字母.经阿狸研究发现,这个打字机是这样工作的: 输入小 ...

  6. POJ 3321 DFS序&plus;线段树

    单点修改树中某个节点,查询子树的性质.DFS序 子树序列一定在父节点的DFS序列之内,所以可以用线段树维护. 1: /* 2: DFS序 +线段树 3: */ 4:   5: #include &lt ...

  7. 【XSY2667】摧毁图状树 贪心 堆 DFS序 线段树

    题目大意 给你一棵有根树,有\(n\)个点.还有一个参数\(k\).你每次要删除一条长度为\(k\)(\(k\)个点)的祖先-后代链,问你最少几次删完.现在有\(q\)个询问,每次给你一个\(k\), ...

  8. F - Change FZU - 2277 (DFS序&plus;线段树)

    题目链接: F - Change FZU - 2277 题目大意: 题意: 给定一棵根为1, n个结点的树. 有q个操作,有两种不同的操作 (1) 1 v k x : a[v] += x, a[v ' ...

  9. BZOJ4551&lbrack;Tjoi2016&amp&semi;Heoi2016&rsqb;树——dfs序&plus;线段树&sol;树链剖分&plus;线段树

    题目描述 在2016年,佳媛姐姐刚刚学习了树,非常开心.现在他想解决这样一个问题:给定一颗有根树(根为1),有以下 两种操作:1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均 ...

随机推荐

  1. Android 手机卫士--自定义组合控件构件布局结构

    由于设置中心条目中的布局都很类似,所以可以考虑使用自定义组合控件来简化实现 本文地址:http://www.cnblogs.com/wuyudong/p/5909043.html,转载请注明源地址. ...

  2. RNN and LSTM saliency Predection Scene Label

    http://handong1587.github.io/deep_learning/2015/10/09/rnn-and-lstm.html  //RNN and LSTM http://hando ...

  3. Using NuGet without committing packages to source control&lpar;在没有把包包提交到代码管理器的情况下使用NuGet进行还原 &rpar;

    外国老用的语言就是谨慎,连场景都限定好了,其实我们经常下载到有用NuGet引用包包然而却没法编译的情况,上谷歌百度搜又没法使用准确的关键字,最多能用到的就是nuget跟packages.config, ...

  4. Swift - 使用CoreLocation实现定位(经纬度、海拔、速度、距离等)

    CoreLocation是iOS中一个提供设备定位的框架.通过这个框架可以实现定位处理,从而获取位置数据,比如经度.纬度.海拔信息等.   1,定位精度的设置 定位服务管理类CLLocationMan ...

  5. 2017&quot&semi;百度之星&quot&semi;程序设计大赛 - 复赛1005&amp&semi;&amp&semi;HDU 6148 Valley Numer【数位dp】

    Valley Numer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  6. &lbrack;pyMongo&rsqb;insert&lowbar;many的Bulkwrite实现机制

    在SQL中,insert many的操作可能会出现插入数据量过大的问题. 印象中MySQL Driver对insert语句的buffer有一个大小限制.超过这个限制的数据可能会被丢弃? -- > ...

  7. Ftp主动模式和被动模式以及java连接ftp模式设置

    Ftp主动模式和被动模式以及java连接ftp模式设置 https://www.cnblogs.com/huhaoshida/p/5412615.html (1) PORT(主动模式) PORT中文称 ...

  8. 逆袭之旅DAY16&period;东软实训&period;Oracle&period;序列

    2018-07-12 14:07:44 序列 序列1.创建序列create sequence 序列名 [increment by n] ---步长 [start with n] ---序列的起始值 序 ...

  9. &lbrack;HNOI2005&rsqb;汤姆的游戏

    嘟嘟嘟 直接O(n ^ 2)暴力判断就行了. 对于圆,判断该点和圆心的距离是否小于半径. 然而为啥我这么写编译不过: scanf("%lf%lf%lf%lf", &a[++ ...

  10. Codeforces Round &num;359 &lpar;Div&period; 2&rpar; B&period; Little Robber Girl&&num;39&semi;s Zoo 水题

    B. Little Robber Girl's Zoo 题目连接: http://www.codeforces.com/contest/686/problem/B Description Little ...