题目()

题目意思：

给定一棵树，树的节点上有权值。接下来会有q次查询。每次查询书上两个节点路径上经过的所有点（包括给出的两个点）权值在[a,b] 这个区间的数求和。每次都是查询这个 s，t，a，b。

解题思路：

按照官方给出的题解，离线+lca。

具体是这样：离线还是要的，我们需要查询s，t这条路径在区间 [a,b] 的数的和。假设 g(x，a，b)：代表树上节点为x的点到根节点这条路径上数字在[a,b] 这个闭区间的数的和。并且假设lca(x,y) 代表x加点与y节点的最近公共祖先。那么每次查询就是:\[g\left ( s,a,b \right )+g(t,a,b)-2*g(lca(s,t),a,b)\]

但是这样计算没有包括lca(s,t)这个点，我们应该特判这个点是否在[a,b]这个区间内部？如果在加上。

所以如何算出需要的g(x,a,b),因为需要的就只有3×q，这么多个。我们发现在遍历这棵树的时候，遍历到一个节点把这个点插入到一个数据结构。遍历完这个点，把这个点删除掉。那么每次遍历到某个点，数据结构里面的点都是这个点到根的所有数字，在这时候我们需要知道数据结构中的数在 [a,b] 这个区间的数字求和是多少？抽象一下，这个数据结构需：

插入一个元素。

删除一个元素。

查询所有元素在[a,b]这个区间的数的和。

我们只需要三个操作。刚好线段树支持这些操作。听说平衡树可以，标程使用 Treap 来维护的。个人线段树用的多，所以就用了线段树。那么线段树节点就维护和，下面有是线段树部分，在结构体封装了。

现在还有 lca，这个的就用倍增随便搞搞。我的处理方法是读入数据，看需要的g(x,a,b)传到树的节点上。遍历树的时候如果有需要的就进行查询操作。

最后输出答案就好，细节可参考本人比较拙的代码。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           using namespace std;typedef long long int LL;const int maxn=1e5+10;struct segtree { struct Node { int lson,rson; LL sum; }T[maxn*32]; int root,sz; int newnode() { sz++; T[sz].lson=T[sz].rson=-1; T[sz].sum=0; return sz; } void init() { sz=-1; root=newnode(); } void insert(int& i,int l,int r,int val) { if(i==-1) i=newnode(); T[i].sum+=val; if(l==r) return ; int mid=(l+r)>>1; if(val<=mid) insert(T[i].lson,l,mid,val); else insert(T[i].rson,mid+1,r,val); } void del(int& i,int l,int r,int val) { if(i==-1) i=newnode(); T[i].sum-=val; if(l==r) return ; int mid=(l+r)>>1; if(val<=mid) del(T[i].lson,l,mid,val); else del(T[i].rson,mid+1,r,val); } LL query(int i,int l,int r,int ql,int qr) { if(i==-1) return 0; if(l==ql&&r==qr) return T[i].sum; int mid=(l+r)>>1; if(qr<=mid) return query(T[i].lson,l,mid,ql,qr); else if(ql>mid) return query(T[i].rson,mid+1,r,ql,qr); else return query(T[i].lson,l,mid,ql,mid)+query(T[i].rson,mid+1,r,mid+1,qr); }}ac;vector
            
             G[maxn];int treeval[maxn],fa[maxn][20],deep[maxn];int n,m;void dfs(int x,int pre){ //printf("dfs x=%d\n",x); fa[x][0]=pre; deep[x]=deep[pre]+1; for(int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=0;i<(int)G[x].size();i++) { int to=G[x][i]; if(to==pre) continue; dfs(to,x); }}int lca(int x,int y){ if (deep[x] < deep[y]) { swap(x, y); } int delta = deep[x] - deep[y]; for (int i = 0; i <= 23; ++i) { if ((delta >> i) & 1) { x = fa[x][i]; } } if (x == y) { return x; } for (int i = 19;i>=0; --i) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0];}struct Query { LL a,b; LL *p; Query(LL _a,LL _b,LL *_p) { a=_a,b=_b; p=_p; }};struct Answer { LL s,t,lca,temp;}ans[maxn];vector
             
              need[maxn];void df(int x,int pre){ // printf("df x=%d\n",x); ac.insert(ac.root,1,1e9,treeval[x]); for(int i=0;i<(int)need[x].size();i++) { LL *p,a=need[x][i].a,b=need[x][i].b; p=need[x][i].p; LL ans=ac.query(ac.root,1,1e9,a,b); *p=ans; // printf("query x=%d a=%lld b=%lld ans=%lld\n",x,a,b,ans); } for(int i=0;i<(int)G[x].size();i++) { int to=G[x][i]; if(to==pre) continue; df(to,x); } ac.del(ac.root,1,1e9,treeval[x]);}int main(){ while(scanf("%d%d",&n,&m)+1) { for(int i=1;i<=n;i++) { G[i].clear(); need[i].clear(); scanf("%d",&treeval[i]); } for(int i=1;i
              
               =a&&treeval[_lca]<=b) ans[i].temp=treeval[_lca]; else ans[i].temp=0; } ac.init(); df(1,0); for(int i=1;i<=m;i++) { //printf("s=%lld t=%lld lca=%lld\n",ans[i].s,ans[i].t,ans[i].lca); LL ff=ans[i].s+ans[i].t-2*ans[i].lca+ans[i].temp; printf(i==m?"%I64d\n":"%I64d ",ff); } } return 0;}