E-Eert Esiwtib

位運算考慮貢獻時分0/1按位模擬考慮
$f_{u,0/1/2}$表示子樹u中點（包括u）到u所有路徑的或/與/異或值。

轉移的時候我們要考慮兩個東西，一個是位運算對于路徑值的影響，另一個是位運算對于所有路徑值的或/與/異或和的影響。

合并子樹的時候自己稍微推下式子即可，按位并且0/1拆分考慮貢獻更容易幫助理解。

Alkaid~題解

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int N=200010; int h[N],e[N],ne[N],op[N],idx; void add(int a,int b,int c){e[idx]=b,ne[idx]=h[a],op[idx]=c,h[a]=idx++;} int n,m; ll val[N]; vector<pair<int,int>> q[105]; ll f[N][3],g[N][3]; ll ans[N][3]; int sz[N]; void update(int u,int v,int op) {if(op==0){f[u][0]|=f[v][0]|val[u];f[u][1]&=f[v][1]|val[u];f[u][2]^=(sz[v]&1?val[u]:0)|(~val[u]&f[v][2]);}else if(op==1){f[u][0]|=f[v][0]&val[u];f[u][1]&=f[v][1]&val[u];f[u][2]^=f[v][2]&val[u];}else{f[u][0]|=(f[v][0]&~val[u])|(~f[v][1]&val[u]);f[u][1]&=(f[v][1]&~val[u])|(~f[v][0]&val[u]);f[u][2]^=(sz[v]&1?val[u]:0)^f[v][2];} } void dfs(int u,int fa) {sz[u]=1;f[u][0]=0; // 或f[u][1]=-1;// 與f[u][2]=0; // 異或for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa) continue;dfs(v,u);sz[u]+=sz[v];update(u,v,op[i]);}memcpy(g[u],f[u],sizeof f[u]);f[u][0]|=val[u];f[u][1]&=val[u];f[u][2]^=val[u]; } int main() {n=rd(),m=rd();memset(h,-1,sizeof h);for(int i=1;i<=n;i++) val[i]=rd<ll>();for(int i=2;i<=n;i++) {int u=rd(),op=rd();add(u,i,op);}for(int i=1;i<=m;i++){int d=rd(),u=rd();q[d].push_back({u,i});}for(int d=0;d<=100;d++){if(d) for(int i=1;i<=n;i++) val[i]+=i;dfs(1,0);for(auto&[u,k]:q[d]) memcpy(ans[k],g[u],sizeof g[u]);}for(int i=1;i<=m;i++) printf("%lld %lld %lld\n",ans[i][0],ans[i][1],ans[i][2]);return 0; }

總結

以上是生活随笔為你收集整理的2021牛客暑期多校训练营5 E-Eert Esiwtib（树形dp+位运算）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。