C++14(g++5.4) 解法, 执行用时: 541ms, 内存消耗: 158184K, 提交时间: 2019-03-19 11:56:22

#include<bits/stdc++.h>
#define lson ls[x],l,mid
#define rson rs[x],mid+1,r
using namespace std;const int N=1e5+7,M=N*20;long long ans[N];
struct data{int to,next;}e[N<<1];int root[N],ls[M],bit[M][18],Bit[18],Size,rs[M],size[M],a[N],head[N],sz,u,v,cnt,n,m,i,j;vector<int>vec[N];
void ins(int u,int v){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v){ins(u,v);ins(v,u);}
void update(int x){
	size[x]=size[ls[x]]+size[rs[x]];
	for(int i=0;i<=17;++i)bit[x][i]=bit[ls[x]][i]+bit[rs[x]][i];
}
int merge(int x,int l,int r,int y){
	if(!x||!y)return x+y;if(l==r)return 0;int mid=l+r>>1;
	ls[x]=merge(lson,ls[y]);rs[x]=merge(rson,rs[y]);
	update(x);return x;
}
void update(int&x,int l,int r,int pos){
	if(!x)x=++sz;size[x]++;for(int i=0;i<=17;++i)bit[x][i]+=pos>>i&1;if(l==r)return;int mid=l+r>>1;
	if(pos<=mid)update(lson,pos);else update(rson,pos);update(x);
} 
void query(int x,int l,int r,int a,int b){
	if(a<=l&&r<=b||!x){for(int i=0;i<=17;++i)Bit[i]+=bit[x][i];Size+=size[x];return;};int mid=l+r>>1;
	if(a<=mid)query(lson,a,b);if(b>mid)query(rson,a,b);
}
void dfs(int x,int fa=0){
	update(root[x],1,n+1,a[x]);
	for(int i=head[x];i;i=e[i].next)if(e[i].to!=fa)dfs(e[i].to,x),root[x]=merge(root[x],1,n+1,root[e[i].to]);
	for(int i=0,id,num;i<vec[x].size();i+=2){
		num=vec[x][i];id=vec[x][i+1];Size=0;memset(Bit,0,sizeof(Bit));
		query(root[x],1,n+1,num+1,n+1);
		for(int j=0;j<=17;++j)ans[id]+=((num>>j&1)?(Size-Bit[j]):Bit[j])*(1LL<<j);
	}
}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;++i)scanf("%d",a+i);
	for(i=1;i<n;++i)scanf("%d%d",&u,&v),insert(u,v);
	for(i=1;i<=m;++i)scanf("%d%d",&u,&v),vec[u].push_back(v),vec[u].push_back(i);
	for(dfs(1),i=1;i<=m;++i)printf("%lld\n",ans[i]);
}

C++11(clang++ 3.9) 解法, 执行用时: 733ms, 内存消耗: 276312K, 提交时间: 2019-02-09 11:48:11

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N=1e5+5;
const int M=4e6+5;
int n,q,w[N],ls[M],rs[M],sz[M],cnt[M][17],rt[N],tot,Sz,Cnt[17];
vector<int>E[N];
void up(int x){
	sz[x]=sz[ls[x]]+sz[rs[x]];
	for(int i=0;i<17;++i)cnt[x][i]=cnt[ls[x]][i]+cnt[rs[x]][i];
}
void modify(int &x,int l,int r,int p){
	x=++tot;
	if(l==r){
		for(int i=0;i<17;++i)cnt[x][i]=p>>i&1;
		sz[x]=1;return;
	}
	int mid=l+r>>1;
	p<=mid?modify(ls[x],l,mid,p):modify(rs[x],mid+1,r,p);
	up(x);
}
int merge(int x,int y,int l,int r){
	if(!x||!y)return x|y;if(l==r)return 0;
	int mid=l+r>>1,z=++tot;
	ls[z]=merge(ls[x],ls[y],l,mid);
	rs[z]=merge(rs[x],rs[y],mid+1,r);
	up(z);return z;
}
void query(int x,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr){
		for(int i=0;i<17;++i)Cnt[i]+=cnt[x][i];
		Sz+=sz[x];return;
	}
	int mid=l+r>>1;
	if(ql<=mid)query(ls[x],l,mid,ql,qr);
	if(qr>mid)query(rs[x],mid+1,r,ql,qr);
}
void dfs(int u,int f){
	modify(rt[u],1,n,w[u]);
	for(int v:E[u])if(v^f)dfs(v,u),rt[u]=merge(rt[u],rt[v],1,n);
}
int main(){
	n=gi();q=gi();
	for(int i=1;i<=n;++i)w[i]=gi();
	for(int i=1;i<n;++i){
		int u=gi(),v=gi();
		E[u].push_back(v);E[v].push_back(u);
	}
	dfs(1,0);
	while(q--){
		int u=gi(),x=gi();
		for(int i=0;i<17;++i)Cnt[i]=0;Sz=0;
		if(x<n)query(rt[u],1,n,x+1,n);
		long long ans=0;
		for(int i=0;i<17;++i)ans+=1ll*((x>>i&1)?Sz-Cnt[i]:Cnt[i])<<i;
		printf("%lld\n",ans);
	}
	return 0;
}