InputThere are multiple cases.
For each case:
The first line contains tow integers n,m(1≤n,m≤10^5), representing the number of cities and the number of situations.
The second line contains n integers c1,c2,...,cn(1≤ci≤10^9), indicating the price of city i‘s specialty.
Then n-1 lines follows. Each line has two integers x,y(1≤x,y≤n), meaning there is road between city x and city y.
Next m line follows. In each line there are four integers s,t,a,b(1≤s,t≤n;1≤a≤b≤10^9), which indicates start city, end city, lower bound of the price, upper bound of the price, respectively, as the exact meaning mentioned in the description above
OutputOutput m space-separated integers in one line, and the ith number should be the answer to the ith situation.Sample Input
5 3 1 2 1 3 2 1 2 2 4 3 1 2 5 4 5 1 3 1 1 1 1 3 5 2 3
Sample Output
7 1 4
思路：
算是比较裸的树链剖分+线段树吧，这道题要求树上任意两点间在区间ab内的值
首先先用树链剖分把这棵树划分轻重链，实际上也是相当于通过类似hash的方式将树形结构变成线形结构
然后就可以用线段树处理了，只要求出在这个区间内的数就行了，直接求出<=b的和<a的做下差就可以了
至于代码的话，树链剖分主要是两个dfs，第一个统计父亲节点fa 当前节点深度deep 子树大小sz ，并在遍历时求出当前节点的重儿子
第二个求出对各个结点的top，对于重儿子来说，top就是沿其所在重链走到顶端的点的位置，对于轻儿子，我们把top定为其本身。
然后对每个结点dfs时先遍历到它的重儿子后遍历轻儿子 最后重链上的点映射到一维数组里得到一串连续的区间，然后就可以直接套线段树了处理了
时间复杂度差不多是是O(nlogn)
实现代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+5; vector<int> vt[maxn]; int n,q,tot; int sz[maxn],deep[maxn],fa[maxn],son[maxn],top[maxn],tree[maxn],pre[maxn]; ll ansl[maxn],ansr[maxn],sum[maxn*4]; struct node1{ int x,id; bool operator < (const node1 &a)const{ return x<a.x; } }a[maxn]; struct node2{ int x,y,a,b,id; }op[maxn]; bool cmp1(const node2 &a,const node2 &b){ return a.a<b.a; } bool cmp2(const node2 &a,const node2 &b){ return a.b<b.b; } void dfs1(int u,int pre,int d){ deep[u] = d; sz[u] = 1; fa[u] = pre; int len = vt[u].size(); for(int i=0;i<len;i++){ int v = vt[u][i]; if(v==pre) continue; dfs1(v,u,d+1); sz[u] += sz[v]; if(!son[v]||sz[v]>sz[son[u]]) son[u] = v; } } void dfs2(int u, int tp){ top[u] = tp; tree[u] = ++tot; pre[tree[u]] = u; if(!son[u]) return ; dfs2(son[u], tp); for(int i = 0, len = vt[u].size(); i < len; i++){ int v = vt[u][i]; if(v != son[u] && v != fa[u]) dfs2(v, v); } } void push_up(int rt){ sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void update(int rt,int l,int r,int pos,int val){ if(l==r){ sum[rt]+=val; return; } int m = (l+r)>>1; if(pos <= m) update(rt<<1,l,m,pos,val); else update(rt<<1|1,m+1,r,pos,val); push_up(rt); } ll query(int rt,int l,int r,int L,int R){ if(L<=l&&R>=r) return sum[rt]; int m = (l+r)>>1; ll ret = 0; if(L<=m) ret += query(rt<<1,l,m,L,R); if(m<R) ret += query(rt<<1|1,m+1,r,L,R); return ret; } ll ask(int x,int y){ //求两结点路径上的权值和 int fx = top[x],fy = top[y]; ll ans = 0; while(fx!=fy){ if(deep[fx]<deep[fy]) swap(fx,fy),swap(x,y); ans += query(1,1,n,tree[fx],tree[x]); x = fa[fx]; fx = top[x]; } ans += (deep[x]>deep[y])?query(1,1,n,tree[y],tree[x]):query(1,1,n,tree[x],tree[y]); return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); while(cin>>n>>q){ tot = 0; memset(son, 0, sizeof(son)); memset(sz, 0, sizeof(sz)); for(int i = 0; i <= n; i++) vt[i].clear(); for(int i=1;i<=n;i++){ cin>>a[i].x;a[i].id=i; } for(int i=1;i<n;i++){ int u,v; cin>>u>>v; vt[u].push_back(v);vt[v].push_back(u); } dfs1(1,0,1); dfs2(1,1); for(int i=1;i<=q;i++){ cin>>op[i].x>>op[i].y>>op[i].a>>op[i].b; op[i].id = i; } memset(sum,0,sizeof(sum)); sort(a+1,a+n+1); sort(op+1,op+q+1,cmp1); for(int i=1,j=1;i<=q;i++){ while(j<=n&&a[j].x<op[i].a){ · update(1,1,n,tree[a[j].id],a[j].x); j++; } ansl[op[i].id] = ask(op[i].x,op[i].y); } memset(sum,0,sizeof(sum)); sort(op+1,op+1+q,cmp2); for(int i = 1, j = 1; i <= q; i++){ while(j <= n && a[j].x <= op[i].b){ update(1, 1, n, tree[a[j].id], a[j].x); j++; } ansr[op[i].id] = ask(op[i].x, op[i].y); //cout<<ansr[op[i].id]<<endl; } for(int i=1;i<=q;i++){ if(i!=1) cout<<" "; cout<<ansr[i]-ansl[i]; } cout<<endl; } return 0; }
原文：http://www.cnblogs.com/kls123/p/7732499.html