给定一棵树，已知每个点点权$w_i$，每次给定$s,t,a,b$，求从s到t的路径上满足$a\le$点权$\le b$的点的点权和。

点数，询问数$\le 10^5$，多组数据，$w_i,a,b\le 10^9$

不正确做法

有一个不正确但是因为数据水可以水过去的做法：

首先树链剖分，显然剖分完要用线段树对吧。

线段树上记录一段区间的最大值和最小值以及和。

每次查找一条重链上满足条件的点权和时，首先定位这个区间，接着做判断：

设区间最小值为$Min$，最大值为$Max$，区间和为$Sum$

如果$a\le Min\le Max \le b$则全部满足，返回$Sum$

如果$Max< a$或$b < Min$则全不满足，返回0

否则递归左半区间和右半区间计算。

显然可以卡飞：

100000 100000
1 100 1 100 1 100...(wi满足1和100交替出现)
1 2
2 3
...(一条链)
1 100000 99 101
1 100000 99 101
1 100000 99 101
1 100000 99 101
1 100000 99 101
1 100000 99 101
...(全部操作全部是这样)

显然每个操作的复杂度被卡到了$O(n)$,T飞。

正确做法

正确做法是树上主席树

通过离散化，设点$i$的权值为$w_i$，排名为$rk_i$（$w_i$相同的点算一个点）

设$s_{i,j}$表示从$i$到根这一条路径上满足$rk_s=j$的i的$w_i$和。

然后强行建可持久化主席树。

显然满足满足$a\le w_s \le b$的点的点s满足$rk_s$在一段区间$[l,r]$里，并且当$rk_s<l$或$r<rk_s$时$w_s<a$或$b<w_s$

然后找出$l,r$

显然从i到根满足$a\le$点权$\le b$的点的点权和$Answer_i$是$\sum_{j=l}^rs_{i,j}$

从s到t满足条件的点的点权和为$Answer_s+Answer_t-Answer_l-Answer_{fa}$

其中l为$LCA(s,t)$，$fa$为$l$的父亲节点。

答案可能爆int，无脑全开ll爆内存，空间限制差评。

/*
Author: CNYALI_LK
LANG: C++
PROG: 6162.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;else if(c==EOF)exit(0);
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
    ll cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
    putchar(end);
}
ll c[102424],l[102424],d[102424];
int ls[2000876],rs[2000876];
ll cnt[2000876],tot;
ll root[102424];
ll to[233333],lst[233333],beg[102424],e;
void ADD(ll u,ll v){
    to[++e]=v;
    lst[e]=beg[u];
    beg[u]=e;
    to[++e]=u;
    lst[e]=beg[v];
    beg[v]=e;
}
int fa[18][102424],t;
#define mid ((l+r)>>1)
ll newtree(ll l,ll r,ll d,ll c){
    ll k=++tot;
    cnt[tot]=(l<=d&&d<=r)*c;
    if(l==r){
        ls[k]=rs[k]=0;
        return k;
    }
    ls[k]=newtree(l,mid,d,c);
    rs[k]=newtree(mid+1,r,d,c);
    return k;
}
ll make(ll x){
    return newtree(1,t,d[x],c[x]);
}
ll copy(ll fa,ll x){
    ll l=1,r=t,k=tot+1,s=root[fa];  
    while(l<=r){
        ++tot;
        cnt[tot]=cnt[s]+c[x];
        ls[tot]=ls[s];
        rs[tot]=rs[s];
        if(l==r)return k;
        if(d[x]<=mid){
            ls[tot]=tot+1;
            s=ls[s];
            r=mid;
        }
        else {
            rs[tot]=tot+1;
            s=rs[s];
            l=mid+1;
        
        }
    }
    return k;
}
ll dep[102424];
void dfs(ll x,ll f){
    dep[x]=dep[f]+1;
    fa[0][x]=f;
    if(!f){
        root[x]=make(x);
    }
    else root[x]=copy(f,x);
    for(ll i=beg[x];i;i=lst[i])if(to[i]!=f)dfs(to[i],x);
}
ll lca(ll u,ll v){
    if(dep[u]<dep[v])swap(u,v);
    for(ll i=17;i+1;--i){
        if(dep[fa[i][u]]>=dep[v])u=fa[i][u];
    }
    for(ll i=17;i+1;--i){
        if(fa[i][u]!=fa[i][v])u=fa[i][u],v=fa[i][v];
    }
    if(u!=v)return fa[0][u];
    else return u;
}
ll sum(ll x,ll l,ll r,ll lx,ll rx){
//  debug("SBYJM %lld,%lld,%lld,%lld,%lld\n",x,l,r,lx,rx);
    if(lx<=l&&r<=rx)return cnt[x];
    if(r<lx||rx<l)return 0;
    return sum(ls[x],l,mid,lx,rx)+sum(rs[x],mid+1,r,lx,rx);
}
ll js(ll x,ll l,ll r){
    if(!x)return 0;
    ll S=sum(root[x],1,t,l,r); 
//  printf("(%lld)\n",S);
    return S;

}
int main(){
#ifdef cnyali_lk
    freopen("6162.in","r",stdin);
    freopen("6162.out","w",stdout);
#endif
    ll n,m;
    while(n=read()){
        m=read();
        for(ll i=1;i<=n;++i){
            c[i]=read();
            l[i]=c[i];
        }
        sort(l+1,l+n+1);
        t=unique(l+1,l+n+1)-(l+1);
        for(ll i=1;i<=n;++i){
            d[i]=lower_bound(l+1,l+t+1,c[i])-l;
    //      printf("%lld->%lld\n",c[i],d[i]);
            beg[i]=0;
        }
        e=0;
        for(ll i=1;i<n;++i){
            ADD(read(),read());
        }
        tot=0;
//      debug("SBYJM\n");
        dfs(1,0);
    /// for(ll i=1;i<=n;++i)printf("%lld\n",fa[0][i]);
//      debug("SBYJM\n");
        for(ll i=1;i<=17;++i)for(ll j=1;j<=n;++j)fa[i][j]=fa[i-1][fa[i-1][j]];
        ll S,T,d,u;
        while(m){
            --m;
    //  debug("SBYJM\n");
            S=read();T=read();d=read();u=read();
    //      printf("%lld,%lld,%lld,%lld\n",S,T,d,u);

            u=upper_bound(l+1,l+t+1,u)-l-1;
            d=lower_bound(l+1,l+t+1,d)-l;
    //      printf("%lld,%lld\n",d,u);
            ll L=lca(S,T);
            write(js(S,d,u)+js(T,d,u)-js(L,d,u)-js(fa[0][L],d,u),m?' ':'\n');

//      debug("sbYJM\n");
        }
//      debug("SBYJM\n");
    }
    return 0;
}

标签: 主席树

添加新评论