题目描述
Chef declared war on Byteland. Chefs best scientist Pramod has designed a new Fighter Plane which can fly with Speed of Light!! So none of the defence forces of Byteland can defeat or defend it.
Byteland has a structure of a tree with $N$ cities connected by $N-1$ bidirectional roads. Each city has index between $[1,n]$ (inclusive) and no two cities have same index. The capital city of Byteland has index $1$. The distance between two cities is the number of roads in the path from one to other.
If the plane drops a bomb on a city $A$, with damage value $X$ then the damage done to a city $B$ will be $\lfloor \frac{X}{2^d}\rfloor$ where $d$ is the distance between $A$ and $B$, note that as the distance of $A$ from itself is $0$, the damage done to $A$ will be $\lfloor \frac{X}{2^0}\rfloor = X$.
Each city has a certain wealth $W_i$ in it, if it is damaged by a value of $X$ then its wealth is reduced by $X$. On a day if the wealth of a city becomes less than or equal to zero then it is considered Economically Dead.
Your task is to write a program that keeps track of the bombings done by the plane and answer the queries asked by the chef. The chef has a total of $Q$ queries for you. There are two types of queries.
- Chef gives you two integers $A$ and $X$, which means that the plane drops a bomb on the city with index $A$ with damage value $X$. A bomb can also be dropped on economically dead city.
- Chef gives you an integer $A$ and you need to print the number of cities that are economically dead which have $A$ in the path from the capital to them.
(See explanation for better understanding)
Constraints
$1 \leq N \leq 10^5$
$1 \leq Q \leq 10^5$
$1 \leq X \leq 10^5$
$1 \leq W_i \leq 10^9$
思路
观察数据范围，发现每次修改的影响范围 $\log X$ 最大不超过 $15$，我们可以猜想算法复杂度和 $\log X$ 相关。
对于更新，考虑到一个子树内深度相同的点在 BFS 序上是连续的一段，我们可以在 BFS 序上建线段树，维护区间的权值最小值。对于每个受影响的深度，直接修改。
因为仍有 $\log X$ 个祖先是受影响的，在更新时应当注意把重复计算的权值消除。
对于查询，考虑一个子树内所有点在 DFS 序上是连续的一段，在 DFS 序上建树状数组，每次更新时遇到权值小于等于 $0$ 的新点就加入树状数组。
那么这道题就非常符合直觉地做完了。
代码
#include <bits/stdc++.h>
#define ll long long
#define inf 1e12
using namespace std;
const int maxn=1e5+1;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
vector<int>to[maxn];
int n,cnt;
int w[maxn],id[maxn],fa[maxn];
int t[maxn],L[maxn],R[maxn];
struct Fen_Tree{
void add(int x){while(x<=n) t[x]++,x+=(x&-x);}
int sum(int x){int r=0;while(x)r+=t[x],x-=(x&-x);return r;}
}FT;
void pre(int u,int f){
fa[u]=f;L[u]=++cnt;
for (int i=0;i<to[u].size();++i){
int v=to[u][i];
if (v!=f) pre(v,u);
}
R[u]=cnt;
}
//---------------------------------------------------
struct Seg_Tree{
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
ll t[maxn<<2],lazy[maxn<<2];
void pushup(int p){
t[p]=min(t[ls],t[rs]);
}
void pushdown(int p){
t[ls]+=lazy[p],lazy[ls]+=lazy[p];
t[rs]+=lazy[p],lazy[rs]+=lazy[p];
lazy[p]=0;
}
void build(int l,int r,int p){
if (l==r) return t[p]=w[id[l]],void();
build(l,mid,ls),build(mid+1,r,rs);
pushup(p);
}
void update(int l,int r,int L,int R,int v,int p){
if (L<=l&&r<=R){t[p]+=v,lazy[p]+=v;return;}
if (lazy[p]) pushdown(p);
if (mid>=R) update(l,mid,L,R,v,ls);
else if (mid<L) update(mid+1,r,L,R,v,rs);
else update(l,mid,L,R,v,ls),update(mid+1,r,L,R,v,rs);
pushup(p);
}
void putout(int l,int r,int p){
if (l==r){FT.add(L[id[l]]),t[p]=inf;return;}
if (lazy[p]) pushdown(p);
if (t[ls]<=0) putout(l,mid,ls);
if (t[rs]<=0) putout(mid+1,r,rs);
pushup(p);
}
}ST;
//---------------------------------------------------
int tim,tag[maxn],lb[maxn][16],rb[maxn][16];
void bfs(){
queue<int>q;
q.push(1);id[tag[1]=++tim]=1;
while(!q.empty()){
int u=q.front();q.pop();
for (int i=0;i<to[u].size();++i){
int v=to[u][i];
if (tag[v]) continue;
id[tag[v]=++tim]=v;
q.push(v);
}
}
for (int i=1;i<=n;++i)
for (int j=0;j<=15;++j)
lb[i][j]=1e7;
for(int i=1;i<=n;i++){
int t=i;
for(int j=0;j<=15;j++){
lb[t][j]=lb[t][j]>tag[i]?tag[i]:lb[t][j];
rb[t][j]=rb[t][j]<tag[i]?tag[i]:rb[t][j];
t=fa[t];
}
}
}
void apply(int u,int v){
int pos=0;
while(v&&rb[u][pos]){
ST.update(1,n,lb[u][pos],rb[u][pos],v,1);
v/=2,pos++;
}
}
void change(int u,int v,int f){
if (f) apply(f,v/2);
apply(u,-v);
if (fa[u]&&(v/2)) change(fa[u],v/2,u);
}
//---------------------------------------------------
int query(int u){
ST.putout(1,n,1);
return FT.sum(R[u])-FT.sum(L[u]-1);
}
int main(){
freopen("pang.in","r",stdin);
freopen("pang.out","w",stdout);
n=read();
for (int i=1;i<=n;++i)
w[i]=read();
for (int i=2;i<=n;++i){
int u=read(),v=read();
to[u].push_back(v);
to[v].push_back(u);
}
pre(1,0);bfs();ST.build(1,n,1);
for (int i=read();i;--i){
int op=read(),u=read();
if (op==1) change(u,read(),0);
else printf("%d\n",query(u));
}
}