华华和月月种树
华华和月月种树
https://ac.nowcoder.com/acm/problem/23051
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+10; vector<int>vec[maxn]; int sumn[maxn],m; int top=1,idmin[maxn],idmax[maxn],b[maxn<<2][4],num,shu[maxn]; int lowbit(int x){ return x&(-x); } void jia(int x,int k){ for(;x<=num;x+=lowbit(x) ) sumn[x]+=k; } int ask(int x){ int ans=0; for(;x;x-=lowbit(x)) ans+=sumn[x]; return ans; } void dfs(int u) { idmin[u]=idmax[u]=++num; for(int i=0;i<vec[u].size();i++ ) { int v=vec[u][i]; dfs(v); idmax[u]=max(idmax[u],idmax[v] ); } } int main() { cin >> m; for(int i=1;i<=m;i++) { for(int j=0,lim=2;j<=lim;j++) { scanf("%d",&b[i][j]); if( b[i][0]!=2 ) lim=1; } b[i][1]++; if( b[i][0]==1 ) vec[ b[i][1] ].push_back(++top) ; } dfs(1); for(int i=1;i<=m;i++) { int q=b[i][1],w=b[i][2]; if( b[i][0]==1 ) { int v=vec[q][shu[q]++ ];//是q的第shu[q]个儿子 int zhi=ask( idmin[v] ); jia( idmin[v],-zhi ); jia( idmin[v]+1,zhi ); } else if( b[i][0]==2 ) { jia( idmin[q],w ); jia( idmax[q]+1,-w); } else printf("%d\n",ask( idmin[q] ) ); } }