## 题目描述

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.

1. 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.
2. 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$

## 代码

#include <bits/stdc++.h>
#define ll long long
#define inf 1e12
using namespace std;
const int maxn=1e5+1;

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{
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 (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);
for (int i=1;i<=n;++i)
}