Born Slippy#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<string> using namespace std; typedef long long ll; int op; ll ans; ll w[100010]; int f[100010]; ll dp[300][300]; ll use[100010][300]; int vis[300]; char str[5]; vector<int>vec[100010]; const int mod=1e9+7; ll opt(ll a,ll b) { if(op==1) return a^b; if(op==2) return a&b; if(op==3) return a|b; } void dfs(int u) { ll a=w[u]>>8; ll b=w[u]&255; ll sum=0; for(int i=0;i<256;i++) if(vis[i]) sum=max(sum,dp[i][b]+(opt(a,i)<<8)); ans=(ans+(u*(sum+w[u])%mod))%mod; vis[a]++; for(int i=0;i<256;i++) { use[u][i]=dp[a][i]; dp[a][i]=max(dp[a][i],sum+opt(b,i)); } for(int i=0;i<vec[u].size();i++) dfs(vec[u][i]); for(int i=0;i<256;i++) dp[a][i]=use[u][i]; vis[a]--; } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d%s",&n,str); if(str[0]=='X') op=1; if(str[0]=='A') op=2; if(str[0]=='O') op=3; for(int i=1;i<=n;i++) vec[i].clear(); memset(vis,false,sizeof(vis)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%lld",&w[i]); } for(int i=2;i<=n;i++) { scanf("%d",&f[i]); vec[f[i]].push_back(i); } ans=0; dfs(1); printf("%lld\n",ans); } return 0; }

感谢叉姐在ICPCCamp上出的这道题最初的原型 -- Data Structure You've Never Heard Of, 同样感谢Claris老师的教导.

由于and, or和xor方法都差不多, 这里仅考虑and操作. 不妨令dp(s)=f(s)−wsdp(s)=f(s)-w_sdp(s)=f(s)−w​s​​, 我们大概要求的就是dp(i)=maxj is ancestor of i{dp(j)+wi and wj}dp(i)=\displaystyle\max_{j \text{ is ancestor of } i}{dp(j)+w_i\text{ and }w_j}dp(i)=​j is ancestor of i​max​​{dp(j)+w​i​​ and w​j​​}. 然后, 显然dp(j)+wi and wjdp(j)+w_i\text{ and }w_jdp(j)+w​i​​ and w​j​​这个式子可以拆成$dp(j)$+[wiw_iw​i​​后8位] and [wjw_jw​j​​后8位] + ([wiw_iw​i​​前8位] and [wjw_jw​j​​前8位]) << 8.

先考虑序列上应该如何做, 即求dp(i)=maxj<i{dp(j)+wi and wj}dp(i)=\displaystyle\max_{j < i}{dp(j)+w_i\text{ and }w_j}dp(i)=​j<i​max​​{dp(j)+w​i​​ and w​j​​}. 考虑这样一个二维数组$ds(x,y)$, 表示对于某个wiw_iw​i​​的后8位为$y$, 对于某个wjw_jw​j​​的前8位为$x$时, $dp(j)$ + [wiw_iw​i​​后8位] and [wjw_jw​j​​后8位]的最值.

如果知道了上述数组, 那么对于某个$i$, 计算$dp(i)$的值就十分方便, 不妨令wi=(a<<8)∣bw_i=(a << 8) | bw​i​​=(a<<8)∣b, 即$a$和$b$分别是wiw_iw​i​​前8位和后8位, 那么只需要枚举wjw_jw​j​​的前8位$x$, 用$ds(x,b)+((a\text{ and }x)<<8)$更新$dp(i)$. 把新的$dp$值更新到$ds(x,y)$也是类似的.

上述方法推广到树上也是十分简单, 由于每次更新$ds(x,y)$的时候只有数组的一维会变动(令$a$=wiw_iw​i​​>>8, 那么只有$ds(a,\cdot )$会变化), 那么只要对数组的第一维做一个可持久化就好了(或者说边dfs边备份).