| WZJ的数据结构（负十） |
| 难度级别：D； 运行时间限制：5000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
给你一个N个节点的有根树，从1到N编号，根节点为1并给出每个点的权值与父亲节点。请你设计一个数据结构，进行以下两种操作： F x v : 将节点x的子树的每个节点权值+v Q x : 询问节点x到其根的路径上的节点权值之和 |
|
输入
|
|
第一行一个正整数N。
接下来N-1行每行一个正整数,分别表示节点2-n的父亲节点编号。 接下来一行N个正整数，表示每个节点的初始权值。 再接下来一行一个正整数M,表示操作的总数。 操作分为以下两种类型。 (1)"Q x"表示询问节点x到其根的路径上的节点权值之和. (2)"F x v"表示将节点x的子树的每个节点权值+v. |
|
输出
|
|
对于每一个操作类型为Q的操作，输出一行一个整数，表示此次询问的答案。
|
|
输入示例
|
|
6
1 1 2 2 2 4 5 7 1 2 3 4 Q 2 F 1 3 Q 2 Q 5 |
|
输出示例
|
|
9
15 20 |
|
其他说明
|
|
1<=N,M<=100000
1<=pi,x<=N 1<=wi<=10^6 1<=v<=1000 |
今天跟健学了DFS序。。。原来就这么回事，注意好符号、出入。
还有，以后的AddEdge注意好顺序！！！
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
typedef long long LL;
const int maxn=+,maxn3=+,inf=-1u>>;
LL addv[maxn3],sumv[maxn3],siz[maxn3],_sum;int n,Q,sig[maxn],A[maxn],si[maxn],so[maxn],cz=,ql,qr,cv;
struct Tedge{int x,y,next;}adj[maxn];int ms=,fch[maxn];
void AddEdge(int u,int v){adj[++ms]=(Tedge){u,v,fch[u]};fch[u]=ms;return;}
void dfs(int u){
si[u]=++cz;sig[cz]=;
for(int i=fch[u];i;i=adj[i].next) dfs(adj[i].y);
so[u]=++cz;sig[cz]=-;
return;
}
void maintain(int o,int L,int R){
int lc=o<<,rc=lc|;
if(L<R) sumv[o]=sumv[lc]+sumv[rc]; else sumv[o]=;
sumv[o]+=addv[o]*siz[o];return;
}
void build(int o,int L,int R){
if(L==R) addv[o]=A[L],siz[o]=sig[L];
else{
int M=L+R>>,lc=o<<,rc=lc|;
build(lc,L,M);build(rc,M+,R);
siz[o]=siz[lc]+siz[rc];
} maintain(o,L,R);return;
}
void update(int o,int L,int R){
if(ql<=L&&R<=qr) addv[o]+=cv;
else{
int M=L+R>>,lc=o<<,rc=lc|;
if(ql<=M) update(lc,L,M);
if(qr>M) update(rc,M+,R);
} maintain(o,L,R);return;
}
void query(int o,int L,int R,int add){
if(ql<=L&&R<=qr) _sum+=add*siz[o]+sumv[o];
else{
int M=L+R>>,lc=o<<,rc=lc|;
if(ql<=M) query(lc,L,M,add+addv[o]);
if(qr>M) query(rc,M+,R,add+addv[o]);
} return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
inline void write(LL x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=;LL buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
inline char readc(){
char tp;for(tp=getchar();!isalpha(tp);tp=getchar());return tp;
}
void init(){
n=read();
for(int i=;i<=n;i++) AddEdge(read(),i); dfs();
for(int i=;i<=n;i++) A[si[i]]=A[so[i]]=read(); build(,,n<<);
return;
}
void work(){
Q=read();
while(Q--){
if(readc()=='Q'){
_sum=;
ql=;qr=si[read()];query(,,n<<,);
write(_sum);ENT;
}
else{
ql=read();
qr=so[ql];ql=si[ql];cv=read();
update(,,n<<);
}
}
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
搜索
复制