树上倍增+差分

时间:2022-12-19 16:41:10
树上倍增+差分树上倍增+差分
  1 #include<bits/stdc++.h>  
  2 //#pragma comment(linker, "/STACK:1024000000,1024000000")   
  3 #include<stdio.h>  
  4 #include<algorithm>  
  5 #include<queue>  
  6 #include<string.h>  
  7 #include<iostream>  
  8 #include<math.h>                    
  9 #include<stack>
 10 #include<set>  
 11 #include<map>  
 12 #include<vector>  
 13 #include<iomanip> 
 14 #include<bitset>
 15 using namespace std;         //
 16 
 17 #define ll long long  
 18 #define ull unsigned long long
 19 #define pb push_back  
 20 #define FOR(a) for(int i=1;i<=a;i++) 
 21 #define sqr(a) (a)*(a)
 22 #define dis(a,b) sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))
 23 ll qp(ll a,ll b,ll mod){
 24     ll t=1;while(b){if(b&1)t=t*a%mod;b>>=1;a=a*a%mod;}return t;
 25 }
 26 struct DOT{ll x;ll y;};
 27 inline void read(int &x){int k=0;char f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())k=k*10+c-'0';x=k*f;} 
 28 const int dx[4]={0,0,-1,1};
 29 const int dy[4]={1,-1,0,0};
 30 const int inf=0x3f3f3f3f; 
 31 const ll Linf=0x3f3f3f3f3f3f3f3f;
 32 const ll mod=1e9+7;;
 33 
 34 const int maxn=2e5+9;  
 35 
 36 int n;
 37  
 38 struct EDGE{
 39     int v;int w;int next;
 40 }G[maxn<<2];
 41 int head[maxn],tot;
 42 
 43 inline void addedge(int u,int v,int w){
 44     ++tot;G[tot].v=v;G[tot].next=head[u];G[tot].w=w;head[u]=tot;
 45 }
 46  
 47 /*
 48 int top[maxn];
 49 int pre[maxn];
 50 int dep[maxn];
 51 int num[maxn];    //子树尺寸
 52 int p[maxn];    //v的对应位置
 53 int out[maxn];  //退出时间戳
 54 int fp[maxn];   //访问序列
 55 int son[maxn];  //重儿子
 56 int pos;        //计时器
 57 */
 58 inline void init(){
 59     memset(head,-1,sizeof head);tot=0;
 60     //memset(son,-1,sizeof son);
 61 }
 62 /*
 63 inline void dfs1(int u,int fa,int d){
 64     dep[u]=d;
 65     pre[u]=fa;
 66     num[u]=1;
 67     for(int i=head[u];~i;i=G[i].next){
 68         int v=G[i].v;
 69         if(v==fa)continue;
 70         dfs1(v,u,d+G[i].w);
 71         num[u]+=num[v];
 72         if(son[u]==-1||num[v]>num[son[u]])son[u]=v;
 73     }
 74 }
 75 inline void getpos(int u,int sp){
 76     top[u]=sp;
 77     p[u]=out[u]=++pos;
 78 
 79     fp[p[u]]=u;
 80     if(son[u]==-1)return;
 81     getpos(son[u],sp);
 82     for(int i=head[u];~i;i=G[i].next){
 83         int v=G[i].v;
 84         if(v!=son[u]&&v!=pre[u])getpos(v,v);
 85     }
 86     out[u]=pos;
 87 }
 88 */
 89 ll add[maxn];
 90 int a[maxn];
 91 
 92 /*
 93 struct NODE{
 94     int l,r;
 95     ll sum;
 96     ll add;
 97 }ST[maxn<<2];
 98 inline void pushup(int rt){
 99     ST[rt].sum=ST[rt<<1].sum+ST[rt<<1|1].sum;
100 }
101 inline void pushdown(int rt){
102     if(ST[rt].add){
103         ST[rt<<1].sum+=ST[rt].add*(ST[rt<<1].r-ST[rt<<1].l+1);
104         ST[rt<<1|1].sum+=ST[rt].add*(ST[rt<<1|1].r-ST[rt<<1|1].l+1);
105         ST[rt<<1].add+=ST[rt].add;
106         ST[rt<<1|1].add+=ST[rt].add;
107         ST[rt].add=0;
108     }
109 }
110 inline void build(int l,int r,int rt){
111     if(l==r){ST[rt].l=ST[rt].r=l;ST[rt].sum=0;return;}
112     ST[rt].l=l;ST[rt].r=r;
113     int m=l+r>>1;
114     build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(rt);
115 }
116 inline void update(int a,int b,int c,int l,int r,int rt){
117     if(a<=l&&b>=r){
118         ST[rt].sum+=(r-l+1)*c;
119         ST[rt].add+=c;
120         return;
121     }
122     int m=l+r>>1;
123     pushdown(rt);
124     if(a<=m)update(a,b,c,l,m,rt<<1);
125     if(b> m)update(a,b,c,m+1,r,rt<<1|1);
126     pushup(rt);
127 }
128 inline ll query(int x,int l,int r,int rt){
129     if(l==r){return ST[rt].sum;}
130     int m=l+r>>1;
131     pushdown(rt);
132     if(x<=m)return query(x,l,m,rt<<1);
133     else return query(x,m+1,r,rt<<1|1);
134 }
135 
136 inline void solve(int u,int v){
137 
138     while(top[u]!=top[v]){
139 
140         if(dep[top[u]]<dep[top[v]])swap(u,v);
141         update(p[top[u]],p[u],1,1,n,1);
142         u=pre[top[u]];
143     }
144 
145     if(dep[u]<dep[v])swap(u,v);
146     
147     //cout<<p[u]<<"ww"<<p[v]<<endl;
148     update(p[v],p[u],1,1,n,1);
149 }
150 */
151 
152 int fa[maxn][50];
153 ll falen[maxn][50];
154 
155 void dfs(int u){
156 
157     for(int i=head[u];~i;i=G[i].next){
158         dfs(G[i].v);
159         add[u]+=add[G[i].v];
160     }
161 }
162 
163 int main(){
164     read(n);
165     init();
166     for(int i=1;i<=n;i++){
167         read(a[i]);
168     }
169     for(int i=2,x,y;i<=n;i++){
170         read(x);read(y);
171         addedge(x,i,y);
172         fa[i][0]=x;
173         falen[i][0]=y;
174     }
175 
176     for(int i=0;i<=32;i++){
177         fa[1][i]=0;
178         falen[0][i]=Linf;
179         falen[1][i]=Linf;
180     }
181     for(int i=1;i<=32;i++){
182         for(int j=1;j<=n;j++){
183             fa[j][i]=fa[fa[j][i-1]][i-1];
184             if(falen[fa[j][i-1]][i-1]==Linf){
185                 falen[j][i]=Linf;continue;
186             }
187             falen[j][i]=falen[fa[j][i-1]][i-1]+falen[j][i-1];
188         }
189     }
190 
191     for(int i=2;i<=n;i++){
192         int now=i;
193         for(int j=32;j>=0;j--){
194             if(falen[now][j] <= a[i]){
195                 a[i]-=falen[now][j];
196                 now=fa[now][j];
197             }
198         }
199 
200         if(i==now)continue;
201         add[fa[i][0]]++;add[fa[now][0]]--;
202     }
203     dfs(1);
204     for(int i=1;i<=n;i++)printf("%lld ",add[i]);
205     //for(int i=1;i<=n;i++)printf("%lld ",query(p[i],1,n,1));
206     
207 }
View Code