D div2 894

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const int MX = 1e6+6;
vector<pair<int,int>> adj[MX];
multiset<pair<int,int>> H[MX];
pair < ll , ll > bit[10*MX];
ll answer[MX];
bool vis[MX];
pair<ll,ll> get(int x)
{
    ll ret = 0,ret2=0;
    while(x)
    {
        ret+=bit[x].first;
        ret2+=bit[x].second;
        x-=x&(-x);
    }
    return {ret,ret2};
}
void nig(int x,ll val)
{
    if(x==0)
        return;
    int dd = x;
    while(x<10*MX)
    {
        bit[x].first+=val;
        bit[x].second+=dd;
        x+=x&(-x);
    }
}
void dfs(int x,int pa,int dis,int CNT,int VAL)
{
    if(vis[x]||dis>1e7)
        return;
    for(auto u : adj[x])
    {
        if(u.first==pa||vis[u.first])continue;
        dfs(u.first,x,dis+u.second,CNT,VAL);
    }
    nig(dis,VAL);
}
void dfs2(int x,int pa,int dis,int CNT,int VAL)
{
    if(vis[x]||dis>1e7)
        return;
    for(auto u : adj[x])
    {
        if(u.first==pa||vis[u.first])continue;
        dfs2(u.first,x,dis+u.second,CNT,VAL);
    }
    for(auto u: H[x])
    {
        if(u.first-dis<0)continue;
        answer[u.second] += get(u.first-dis).first*u.second - get(u.first-dis).second+1;
    }
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int L;scanf("%d",&L);
        adj[(i+1)/2].push_back({i+1,L});
    }
    for(int i=1;i<=m;i++)
    {
        int h;scanf("%d",&h);
        H[i].insert({h,i});
    }
    for(int cnt = 1;cnt<= n;cnt++){
        if(adj[cnt].empty())continue;
       auto u1  = adj[cnt][0];
       pair < int , int > u2 = {0,0};
       if(adj[cnt].size()>1)
        u2 = adj[cnt][1];
        dfs(u1.first,u1.second,1,cnt,1);
        dfs2(u2.first,0,u2.second,0,cnt);
        dfs(u1.first,u1.second,1,cnt,-1);
        swap(u1,u2);
        dfs(u1.first,u1.second,1,cnt,1);
        dfs2(u2.first,0,u2.second,0,cnt);
        dfs(u1.first,u1.second,1,cnt,-1);
        vis[cnt] =1;
    }
    for(int i=1;i<=m;i++)
    {
        cout<<answer[i]<<'\n';
    }
    return 0;
}