题目链接
https://ac.nowcoder.com/acm/contest/368/F
思路
询问可以离线。
然后每个节点上建32个权值线段树(权值不大，其实只要20颗)
记录每一位权值为x(如果是根节点的话)的01和
然后从根节点向上合并。
访问到需要访问的就查询。
大体这样，不过细节和处理极其恶心(毒瘤mjt或者我码力太差)
合并的时候。
因为两个数字相同要，合并到底的时候要这样.
if(!siz[a]&&!siz[b]) return a;
if(siz[a]==siz[b]) {
for(int i=0;i<=20;++i) xo[a][i]=0;
siz[a]=0;siz[b]=0;
} else {
for(int i=0;i<=20;++i) xo[a][i]=(bool)((1<<i)&l);
siz[a]=1,siz[b]=0;
}
return a;
因为要异或上x，所以就要讨论子树中0的个数，因为出现两个的树的删去了，还要维护siz
空间\时间复杂度是\(nlog^2\)
代码
/*
询问可以离线。
然后每个节点上建32个权值线段树(权值不大，其实只要20颗)
记录每一位权值为x(如果是根节点的话)的01和
然后从根节点向上合并。
访问到需要访问的就查询。
大体这样，不过细节和处理极其恶心(毒瘤mjt或者我码力太差)
合并的时候。
因为两个数字相同要，合并到底的时候要这样
if(!siz[a]&&!siz[b]) return a;
if(siz[a]==siz[b]) {
for(int i=0;i<=20;++i) xo[a][i]=0;
siz[a]=0;siz[b]=0;
} else {
for(int i=0;i<=20;++i) xo[a][i]=(bool)((1<<i)&l);
siz[a]=1,siz[b]=0;
}
return a;
因为要异或上x，所以就要讨论子树中0的个数，因为出现两个的树的删去了，还要维护siz
空间\时间复杂度是$nlog^2$
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
vector<int> G[N];
int n,m,w[N],cnt;
long long ans[N];
vector<pair<int,int> > Q[N];
int ls[N*20],rs[N*20],xo[N*20][21],rt[N*20],siz[N*20];
void pushup(int rt) {
for(int i=0;i<=20;++i)
xo[rt][i]=xo[ls[rt]][i]+xo[rs[rt]][i];
siz[rt]=siz[ls[rt]]+siz[rs[rt]];
}
int zibi;
int merge(int l,int r,int a,int b) {
if(!a||!b) return a+b;
if(l==r) {
if(!siz[a]&&!siz[b]) return a;
if(siz[a]==siz[b]) {
for(int i=0;i<=20;++i) xo[a][i]=0;
siz[a]=0;siz[b]=0;
} else {
for(int i=0;i<=20;++i) xo[a][i]=(bool)((1<<i)&l);
siz[a]=1,siz[b]=0;
}
return a;
}
int mid=(l+r)>>1;
ls[a]=merge(l,mid,ls[a],ls[b]);
rs[a]=merge(mid+1,r,rs[a],rs[b]);
pushup(a);
return a;
}
void insert(int &now,int l,int r,int k) {
now=++cnt;
if(l==r) {
for(int i=0;i<=20;++i) xo[now][i]=(bool)((1<<i)&k);
siz[now]=1;
return;
}
int mid=(l+r)>>1;
if(k<=mid) insert(ls[now],l,mid,k);
else insert(rs[now],mid+1,r,k);
pushup(now);
}
int query(int l,int r,int k,int dep,int rt) {
if(!rt||r<=k) return 0;
if(l>k) return xo[rt][dep];
int mid=(l+r)>>1;
// int ans=0;
if(k<=mid) return query(mid+1,r,k,dep,rs[rt])+query(l,mid,k,dep,ls[rt]);
// if(k>mid)
return query(mid+1,r,k,dep,rs[rt]);
}
int query_siz(int l,int r,int k,int rt) {
if(!rt||r<=k) return 0;
if(l>k) return siz[rt];
int mid=(l+r)>>1;
// int ans=0;
if(k<=mid) return query_siz(mid+1,r,k,rs[rt])+query_siz(l,mid,k,ls[rt]);
// if(k>mid)
return query_siz(mid+1,r,k,rs[rt]);
}
void dfs(int u,int f) {
insert(rt[u],1,n,w[u]);
for(vector<int>::iterator it=G[u].begin();it!=G[u].end();++it) {
if(*it==f) continue;
dfs(*it,u);
rt[u]=merge(1,n,rt[u],rt[*it]);
}
for(vector<pair<int,int> >::iterator it=Q[u].begin();it!=Q[u].end();++it) {
for(int i=0;i<=20;++i) {
int js=query_siz(1,n,it->first,rt[u]);
if(it->first&(1<<i)) {
ans[it->second]+=(1LL<<i)*(long long)(js-query(1,n,it->first,i,rt[u]));
} else {
ans[it->second]+=(1LL<<i)*(long long)query(1,n,it->first,i,rt[u]);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&w[i]);
for(int i=2;i<=n;++i) {
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=1;i<=m;++i) {
int u,x;
scanf("%d%d",&u,&x);
Q[u].push_back(make_pair(x,i));
}
dfs(1,0);
for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
return 0;
}