题解：P7310 [COCI2018-2019#2] Deblo

dayz_break404 · 2024-10-07 15:30:50 · 题解

注意到位运算每一位都是独立的，考虑将权值的每一位拆开，单独考虑每一位对答案的贡献。

先枚举每一位，这样原树就变成了一颗只有 0 和 1 的树。很明显只有当路径上的 1 的个数为奇数时，这条路径才会对答案产生贡献。

记 dp_{u,0} 表示路径的一个端点为 u，另一个端点在 u 的子树，路径上的 1 的个数为偶数时，这样的路径的条数。同理 dp_{u,1} 为 1 的个数为奇数。

转移时进行分类讨论：

• 若当前的节点 u 第 w 位是 1，那么对于其每一个子节点 v，有 dp_{u,0}+=dp_{v,1},dp_{u,1}+=dp_{v,0}。
• 若当前的节点 u 第 w 位是 0，那么对于其每一个子节点 v，有 dp_{u,0}+=dp_{v,0},dp_{u,1}+=dp_{v,1}。

考虑如何计算答案，显然对于一条路径只有两种情况：

时间复杂度 O(n\log V)，其中 V 为值域。

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
#define ll long long
const int maxn=1e5+20;
int a[maxn],n,head[maxn],idx,dp[maxn][2],mul[40];
ll ans;
struct node{
    int nxt,to;
}e[maxn<<1];
inline void add(int u,int v){
    e[++idx].to=v,e[idx].nxt=head[u],head[u]=idx;
}
void dfs(int u,int fa,int w){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u,w);
        ans+=1ll*dp[u][1]*dp[v][0]*mul[w]+1ll*dp[u][0]*dp[v][1]*mul[w];
        if(a[u]&1) dp[u][0]+=dp[v][1],dp[u][1]+=dp[v][0];
        else dp[u][0]+=dp[v][0],dp[u][1]+=dp[v][1];
    }
    dp[u][a[u]&1]++;
    ans+=1ll*dp[u][1]*mul[w];
}
int main(){
    mul[0]=1;
    for(int i=1;i<=30;i++) mul[i]=mul[i-1]*2;
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    int u,v;
    for(int i=1;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);
    for(int i=0;i<=30;i++){
        dfs(1,0,i);
        for(int j=1;j<=n;j++) a[j]>>=1,dp[j][0]=dp[j][1]=0;
    }
    printf("%lld\n",ans);
    return 0;
}