HDU6162 Ch's gift
给定一棵树，已知每个点点权\(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;
}