Tree

https://nanti.jisuanke.com/t/39272
题意：给你一颗树，结点权值告诉你，你有如下三种操作
1 s t 修改从1到s的路径上的所有点，a[i]=a[i]|t
2 s t 修改从1到s的路径上的所有点，a[i]=a[i]&t
3 s t 询问将1到s的路径上的所有点作为石头堆，再加上一个个数为t的石头堆，进行一次尼姆(nim)博弈，先手胜利输出YES，否则输出NO

前置知识：
nim博弈先手的必胜条件为，n堆石头的异或和不为0,也即a[1] ^ a[2] ^a[3] . . .^a[n]!=0
所以问题就转为了a[1] ^ a[2] ^ a[] . . .^ a[s] ^ a[t]是否为0，为0输出YES，否则输出NO

分析：这道题的1，2操作是对树上的一条链进行|，&操作，所以需要用到树链剖分，并且用线段树去维护异或和，对于所有数的二进制的每一位，我们都需要开一颗线段树去维护，这里数最大1e9，所以二进制位最多31位，我们需要开31一颗线段树去分别维护即可.

AC代码：

#include<bits/stdc++.h>
#define ls dep<<1
#define rs dep<<1|1
using namespace std;
const int Maxn = 1e5+10;
struct Edge{
int v;
int next;
}edge[Maxn*2];
int head[Maxn];
int fa[Maxn];
int siz[Maxn];
int son[Maxn];
int dep[Maxn];
int dfn[Maxn];
int top[Maxn];
int a[Maxn];
int tim=0;
int sum[31][Maxn*4]={0};//线段树区间和 
int lz[31][Maxn*4]={0};//延迟标记
int cnt = 0;
int N,M;
void init(){
memset(head,-1,sizeof(head));
return ;
}
void build(int u,int v){
edge[++cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt;
edge[++cnt].v = u;
edge[cnt].next = head[v];
head[v] = cnt;
return ;
}
void dfs1(int u,int f){
fa[u] = f;
dep[u] = dep[f]+1;
siz[u] = 1;
int maxsonsize = -1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v = edge[i].v;
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>maxsonsize){
maxsonsize = siz[v];
son[u] = v;
}
}
return ;
}
void dfs2(int u,int t){
dfn[u] = ++tim;
top[u] = t;
if(!son[u]) return ;
dfs2(son[u],t);
for(int i=head[u];i!=-1;i=edge[i].next){
int v = edge[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
return ;
}
void pushup(int pos,int dep){
sum[pos][dep] = sum[pos][ls]+sum[pos][rs];
return ;
}
void pushdown(int pos,int dep,int l,int r){
if(lz[pos][dep]==-1){
int mid = l+r>>1;
lz[pos][ls]=lz[pos][rs]=-1;
sum[pos][ls]=sum[pos][rs] = 0;
lz[pos][dep] = 0;
}
else if(lz[pos][dep]==1){
int mid = l+r>>1;
lz[pos][ls]=lz[pos][rs]=1;
sum[pos][ls]=(mid-l+1);
sum[pos][rs]=(r-mid);
lz[pos][dep] = 0;
}
return ;
}
void modify(int pos,int l,int r,int ql,int qr,int dep,int val){
if(ql<=l&&r<=qr){
if(val==-1) sum[pos][dep] = 0;
else sum[pos][dep] = (r-l+1);
lz[pos][dep] = val;
return ;
}
pushdown(pos,dep,l,r);
int mid = l+r>>1;
if(ql<=mid) modify(pos,l,mid,ql,qr,ls,val);
if(qr>mid) modify(pos,mid+1,r,ql,qr,rs,val);
pushup(pos,dep);
return ;
}
void mchain(int pos,int x,int y,int val){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
modify(pos,1,N,dfn[top[x]],dfn[x],1,val);
x = fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
modify(pos,1,N,dfn[x],dfn[y],1,val);
return ;
}
int query(int pos,int l,int r,int ql,int qr,int dep){
if(ql<=l&&r<=qr){
return sum[pos][dep];
}
pushdown(pos,dep,l,r);
int ans = 0;
int mid = l+r>>1;
if(ql<=mid) ans+=query(pos,l,mid,ql,qr,ls);
if(qr>mid)
ans+=query(pos,mid+1,r,ql,qr,rs);
pushup(pos,dep);
return ans;
}
int qchain(int pos,int x,int y){
int ans = 0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(pos,1,N,dfn[top[x]],dfn[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(pos,1,N,dfn[x],dfn[y],1);
return ans;
}
bool check(int pos,int val,int s){
int ans = qchain(pos,1,s);
ans&=1;
if(ans&&val) return true;
if(!ans&&!val) return true;
return false;
}
int main(){
init();
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
for(int i=1;i<N;i++){
int u,v;
scanf("%d %d",&u,&v);
build(u,v);
}
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=N;i++){
for(int k=0;k<31;k++){
int val = (1<<k)&a[i];
if(val) modify(k,1,N,dfn[i],dfn[i],1,1);
}
}
while(M--){
int op,s,t;
scanf("%d %d %d",&op,&s,&t);
if(op==1){
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(val) mchain(i,1,s,1);
}
}
else if(op==2){
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(!val) mchain(i,1,s,-1);
}
}
else{
int flag = 1;
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(!check(i,val,s)){
flag = 0;
break;
}
}
if(!flag) printf("YESn");
else printf("NOn");
}
}
return 0;
}

最后

以上就是着急鲜花为你收集整理的2019ICPC西安邀请赛E题，线段树+述链剖分+nim博弈Tree的全部内容，希望文章能够帮你解决2019ICPC西安邀请赛E题，线段树+述链剖分+nim博弈Tree所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。