这题一开始把我看愣了。难道是线段树套树状数组?空间根本开不下好不好!!!
后来想到维护区间极值,从而排除不必要情况,降低复杂度。
无需修改,码量顿减……
注意,同一组数据放一行,注意行末空格。
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=500000; int n,m,val[maxn]; int beg[maxn],nex[maxn],to[maxn],e; void add(int x,int y){ e++;nex[e]=beg[x]; beg[x]=e;to[e]=y; } int son[maxn],size[maxn],dep[maxn],f[maxn]; void dfs1(int x,int fa){ dep[x]=dep[fa]+1; f[x]=fa; size[x]=1; son[x]=0; for(int i=beg[x];i;i=nex[i]){ int t=to[i]; if(t==fa)continue; dfs1(t,x); size[x]+=size[t]; if(size[t]>size[son[x]]) son[x]=t; } } int id[maxn],num[maxn],top[maxn],cnt; void dfs2(int x,int topc){ id[x]=++cnt; num[cnt]=val[x]; top[x]=topc; if(!son[x])return; dfs2(son[x],topc); for(int i=beg[x];i;i=nex[i]){ int t=to[i]; if(t==son[x]||t==f[x]) continue; dfs2(t,t); } } int tr[maxn],mx[maxn],mn[maxn]; void build(int h,int l,int r){ if(l==r){ mx[h]=mn[h]=tr[h]=num[l]; return; } int mid=(l+r)>>1; build(h<<1,l,mid); build(h<<1|1,mid+1,r); tr[h]=tr[h<<1]+tr[h<<1|1]; mx[h]=max(mx[h<<1],mx[h<<1|1]); mn[h]=min(mn[h<<1],mn[h<<1|1]); } int query(int h,int l,int r,int x,int y,int a,int b){ if(l>y||r<x||mx[h]<a||mn[h]>b)return 0; if(l>=x&&r<=y&&mn[h]>=a&&mx[h]<=b)return tr[h]; int mid=(l+r)>>1; return query(h<<1,l,mid,x,y,a,b)+query(h<<1|1,mid+1,r,x,y,a,b); } int qc(int x,int y,int a,int b){ int ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); ans+=query(1,1,n,id[top[x]],id[x],a,b); x=f[top[x]]; } if(dep[x]>dep[y])swap(x,y); ans+=query(1,1,n,id[x],id[y],a,b); return ans; } signed main(){ while(scanf("%lld%lld",&n,&m)!=EOF){ e=cnt=0; memset(beg,0,sizeof(beg)); for(int i=1;i<=n;i++) scanf("%lld",&val[i]); int x,y; for(int i=1;i<n;i++){ scanf("%lld%lld",&x,&y); add(x,y),add(y,x); } dfs1(1,0); dfs2(1,1); build(1,1,n); int a,b; for(int i=1;i<=m;i++){ scanf("%lld%lld%lld%lld",&x,&y,&a,&b); printf("%lld",qc(x,y,a,b)); if(i!=m)printf(" "); } puts(""); } return 0; }
深深地感到自己的弱小。