COJ 0990 WZJ 의 데이터 구조 (마이너스 10)

WZJ 의 데이터 구조 (마이너스 10)
난이도 레벨: D;운행 시간 제한: 5000 ms;실행 공간 제한: 51200 KB;코드 길이 제한: 2000000 B
시험 문제 설명
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 인 조작 에 대해 한 줄 의 정 수 를 출력 하여 이번 질문 의 답 을 나타 낸다.
예제 입력
6112224 5 7 1 2 34Q 2F 1 3Q 2Q 5
출력 예시
91520
기타 설명
1<=N,M<=100000
1<=pi,x<=N
1<=wi<=10^6
1<=v<=1000
오늘 건 이랑 DFS 서 를 배 웠 는데...원래 이런 일이 있 었 으 니 기호 와 출입 에 주의해 라.
그리고 앞으로 AddEdge 순서 조심!!!

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 #define PAU putchar(' ')
 8 #define ENT putchar('
')
 9 using namespace std;
10 typedef long long LL;
11 const int maxn=200000+10,maxn3=600000+10,inf=-1u>>1;
12 LL addv[maxn3],sumv[maxn3],siz[maxn3],_sum;int n,Q,sig[maxn],A[maxn],si[maxn],so[maxn],cz=0,ql,qr,cv;
13 struct Tedge{int x,y,next;}adj[maxn];int ms=0,fch[maxn];
14 void AddEdge(int u,int v){adj[++ms]=(Tedge){u,v,fch[u]};fch[u]=ms;return;}
15 void dfs(int u){
16     si[u]=++cz;sig[cz]=1;
17     for(int i=fch[u];i;i=adj[i].next) dfs(adj[i].y);
18     so[u]=++cz;sig[cz]=-1;
19     return;
20 }
21 void maintain(int o,int L,int R){
22     int lc=o<<1,rc=lc|1;
23     if(L<R) sumv[o]=sumv[lc]+sumv[rc]; else sumv[o]=0;
24     sumv[o]+=addv[o]*siz[o];return;
25 }
26 void build(int o,int L,int R){
27     if(L==R) addv[o]=A[L],siz[o]=sig[L];
28     else{
29         int M=L+R>>1,lc=o<<1,rc=lc|1;
30         build(lc,L,M);build(rc,M+1,R);
31         siz[o]=siz[lc]+siz[rc];
32     } maintain(o,L,R);return;
33 }
34 void update(int o,int L,int R){
35     if(ql<=L&&R<=qr) addv[o]+=cv;
36     else{
37         int M=L+R>>1,lc=o<<1,rc=lc|1;
38         if(ql<=M) update(lc,L,M);
39         if(qr>M) update(rc,M+1,R);
40     } maintain(o,L,R);return;
41 }
42 void query(int o,int L,int R,int add){
43     if(ql<=L&&R<=qr) _sum+=add*siz[o]+sumv[o];
44     else{
45         int M=L+R>>1,lc=o<<1,rc=lc|1;
46         if(ql<=M) query(lc,L,M,add+addv[o]);
47         if(qr>M) query(rc,M+1,R,add+addv[o]);
48     } return;
49 }
50 inline int read(){
51     int x=0,sig=1;char ch=getchar();
52     while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();}
53     while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
54     return x*=sig;
55 }
56 inline void write(int x){
57     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
58     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
59     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
60 }
61 inline void write(LL x){
62     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
63     int len=0;LL buf[15];while(x)buf[len++]=x%10,x/=10;
64     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
65 }
66 inline char readc(){
67     char tp;for(tp=getchar();!isalpha(tp);tp=getchar());return tp;
68 }
69 void init(){
70     n=read();
71     for(int i=2;i<=n;i++) AddEdge(read(),i); dfs(1);
72     for(int i=1;i<=n;i++) A[si[i]]=A[so[i]]=read(); build(1,1,n<<1);
73     return;
74 }
75 void work(){
76     Q=read();
77     while(Q--){
78         if(readc()=='Q'){
79             _sum=0;
80             ql=1;qr=si[read()];query(1,1,n<<1,0);
81             write(_sum);ENT;
82         }
83         else{
84             ql=read();
85             qr=so[ql];ql=si[ql];cv=read();
86             update(1,1,n<<1);
87         }
88     }
89     return;
90 }
91 void print(){
92     return;
93 }
94 int main(){init();work();print();return 0;}

 
수색 하 다.
복제 하 다.