【题目描述】给定一颗树，每个点有各自的权值，任意选取两个点，要求算出这两个点路径上所有点的and,or,xor的期望值。
【数据范围】n<=10^5
首先期望可以转化为求树上所有点对的and,or,xor值的和，然后在除以n*n就可以了，对于权值，我们可以按位做，这样问题就转化为了给定一棵树，树上的点的权值为0或者1，我们需要求出来点对的and,or,xor值，这个问题我们可以取任意节点当做根，然后用tree-dp来解决
and：这个比较好处理，我们只需要记录每个节点x，p为x子树中一点，x到p的路径上全部为1，这样的p的点的数量，这个比较容易转移，记录这个为sum，那么
sum[x]=Σsum[p] col[x]==1
sum[x]=0 col[x]==0 col为颜色。
维护了这个东西之后我们就可以处理答案了，对于所有x的点对，有两种情况，第一种是一端点是x，另一端点是x子树中的点，对于这样的点，我们只需要累加sum[son of x]就可以了，因为x颜色可能是0，所以我们不能直接加sum[x]，还有一种情况是这个点对在x的子树中，且路径经过x，那么这样的点对我们只需要记录一个tot代表Σsum[son of x]然后对于x的每一个子节点p，我们需要累加答案sum[p]*(tot-sum[p])，这样就可以了。
or：维护一个num数组，设p为x的子树中一点，那么num[x]为所有x到p的路径上存在一个1的p的个数，设size[x]表示以x为根节点那么
num[x]=size[x] col[x]==1
num[x]=Σnum[p] col[x]==0
这样我们就可以求出来num[x]了，对于答案的累加类似于and的累加，对于跨根的，我们只需要使路径的一部分有1就好了，也就是ans+=num[p]*(size[x]-size[p]-1)。
xor：我们可以维护一个a0[x]和a1[x]代表以x为根的子树中，p为其中一点，x到p的路径上1的个数为奇/偶的p的点的数量，那么比较显然的是
a0[x]=Σa1[p] a1[x]=Σa0[p] col[x]==1
a0[x]=Σa0[p] a1[x]=Σa1[p] col[x]==0
这个的累加答案也类似于上面，我们需要用a0[p]和a1[p]来累加答案。
反思：比赛的时候没考虑到然后栈溢出了，后来改成bfs就好了。
//By BLADEVIL#include#include #define maxn 100010#define LL long long#pragma comment(linker,"/STACK:102400000,102400000")using namespace std;LL n,l;LL pre[maxn<<1],other[maxn<<1],last[maxn],key[maxn],color[maxn],sum[maxn],size[maxn],num[maxn],a0[maxn],a1[maxn],que[maxn],flag[maxn],father[maxn];LL ans,ANS,ANSor,ansor,ANSx,ansx;void connect(LL x,LL y) { //printf("%d %d %d\n",x,y,l); pre[++l]=last[x]; last[x]=l; other[l]=y;}void update(LL x){ //printf("%d ",x); sum[x]=color[x]; size[x]=1; num[x]=0; if (color[x]) a1[x]=1,a0[x]=0; else a0[x]=1,a1[x]=0; for (LL p=last[x];p;p=pre[p]) { if (other[p]==father[x]) continue; size[x]+=size[other[p]]; } if (sum[x]) { LL tot=0; for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) ans+=2*sum[other[p]],tot+=sum[other[p]]; for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) ans+=sum[other[p]]*(tot-sum[other[p]]); sum[x]+=tot; } if (color[x]) { for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) ansor+=size[other[p]]*(size[x]-size[other[p]]); num[x]=size[x];ansor+=num[x]; } else { LL tot=size[x]; for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) ansor+=2*num[other[p]]*(tot-size[other[p]]),num[x]+=num[other[p]],tot-=num[other[p]]; } if (color[x]) { LL tot0=0,tot1=0; for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) tot0+=a0[other[p]],tot1+=a1[other[p]]; ansx+=2*tot0+1; for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) ansx+=2*a0[other[p]]*(tot0-a0[other[p]]),tot0-=a0[other[p]]; for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) ansx+=2*a1[other[p]]*(tot1-a1[other[p]]),tot1-=a1[other[p]]; for (LL p=last[x];p;p=pre[p]) if(other[p]!=father[x]) a1[x]+=a0[other[p]],a0[x]+=a1[other[p]]; } else { LL tot0=0,tot1=0; for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) tot0+=a0[other[p]],tot1+=a1[other[p]]; ansx+=2*tot1; for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) ansx+=2*a1[other[p]]*(tot0-a0[other[p]]); for (LL p=last[x];p;p=pre[p]) if (other[p]!=father[x]) a1[x]+=a1[other[p]],a0[x]+=a0[other[p]]; } //printf("%d %d\n",x,ansor); //printf("%d %d\n",x,ansx);}int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); LL task,x,y; scanf("%lld",&task); while (task--) { memset(last,0,sizeof last); memset(flag,0,sizeof flag); l=0; ANS=ANSor=ANSx=0; scanf("%lld",&n); for (LL i=1;i<=n;i++) scanf("%lld",&key[i]); for (LL i=1;i