#1790. 小A的树

题目描述

小`A`有一棵 $N$ 个点的树，每个点都有一个小于 $2^{20}$ 的非负整数权值。现在小`A`从树中随机选择一个点 $x$ ，再随机选择一个点 $y$ （ $x,y$ 可以是同一个点），并对从 $x$ 到 $y$ 的路径上所有的点的权值分别做 $ ext{and}$ 、 $ ext{or}$ 、 $ ext{xor}$ 运算，最终会求得三个整数。小`A`想知道，他求出的三个数的期望值分别是多少。

题解

考虑拆位，即我们考虑一棵点权为 $0/1$ 的树，操作后为 $1$ 的链有多少条。

于是做个 $ ext{dp}$ ： $f[i][0/1]$ 表示 $i$ 子树内，到 $i$ 经操作后为 $0/1$ 的链有多少条，每次 $son$ 合并上来的时候计算答案即可。

效率： $O(20n)$ 。

代码

#include <bits/stdc++.h>
#define db double
using namespace std;
const int N=1e5+5;db k,s[3];
int T,n,hd[N],V[N<<1],nx[N<<1],t,f[3][2][N],a[N],b[N];
void add(int u,int v){
    nx[++t]=hd[u];V[hd[u]=t]=v;
}
void dfs(int u,int fr){
    for (int j=0;j<3;j++)
        f[j][b[u]][u]=1,f[j][!b[u]][u]=0;
    for (int v,i=hd[u];i;i=nx[i]){
        if ((v=V[i])==fr) continue;dfs(v,u);
        s[0]+=k*f[0][1][u]*f[0][1][v];
        s[1]+=k*f[1][1][u]*f[1][1][v]+k*f[1][1][u]*f[1][0][v]+k*f[1][0][u]*f[1][1][v];
        s[2]+=k*f[2][0][u]*f[2][1][v]+k*f[2][1][u]*f[2][0][v];
        for (int j=0;j<2;j++)
            f[0][j&b[u]][u]+=f[0][j][v],
            f[1][j|b[u]][u]+=f[1][j][v],
            f[2][j^b[u]][u]+=f[2][j][v];
    }
}
void work(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for (int i=1,u,v;i<n;i++)
        scanf("%d%d",&u,&v),
        add(u,v),add(v,u);
    k=1;s[0]=s[1]=s[2]=0;
    for (int i=0;i<20;i++){
        for (int j=1;j<=n;j++){
            b[j]=(a[j]>>i)&1;
            if (b[j]) s[0]+=k,s[1]+=k,s[2]+=k;
        }
        k*=2;dfs(1,0);
    }
    for (int i=0;i<3;i++)
        printf("%.3lf%c",s[i]/(1.*n*n),i<2?' ':'
');
    for (int i=1;i<=n;i++) hd[i]=0;t=0;
}
int main(){for (cin>>T;T--;work());return 0;}