本文共 1626 字，大约阅读时间需要 5 分钟。

刚好在$gym$碰到就顺手写了

话说打长春的时候是被队友秒掉的emm

自己写的时候还是有点细节的…

注意虽然这是一颗有根树,但边并不是完全由父亲指向儿子的!!!

需要建双向边,我被这个卡疯了…

$$\sum _{i=1}^n\sum _{j=i+1}^n[a_i\oplus a_j=a_{lc{a}_{i,j}}]\ast (i\oplus j)$$

发现可以枚举每个点作为$lca$来计算贡献

那么对于$u$子树内的点$v$

若子树中存在另外的节点$k$满足$a_k=a_u\oplus a_k$就可以产生贡献

发现快速找到$a_u\oplus a_k$只需要开个桶即可

$val[i][j][0/1]$表示当前子树内$a$值为$i$的节点中,二进制第$j$位有多少个节点是$0/1$

那么这个数字可以用树上启发式合并处理

然后就是枚举子树内每个点,一边计算贡献,一边把子树加入数组

#include 
   
    using namespace std;const int maxn = 1e6+10;const int N = 1e5+10;vector
    
     vec[N];int n,a[N],dfn[N],low[N],top[N],id,siz[N],son[N];void dfs(int u,int fa){
   	siz[u] = 1; dfn[u] = ++id; top[id] = u;	for( auto v:vec[u] )	{
   		if( v==fa )	continue;		dfs(v,u);		siz[u] += siz[v];		if( siz[son[u]]
     
      >q)&1] += w;	}void calc(int u,int fa){
   	update( u,1 );	for( auto v:vec[u] )	{
   		if( v==SON || v==fa )	continue;		for(int j=dfn[v];j<=low[v];j++)		{
   			int ID = top[j];			for(int q=0;q<=20;q++)				if( (a[u]^a[ID])<=1e6 )					ans += 1ll*(1<
      
       >q)&1)];		}		for(int j=dfn[v];j<=low[v];j++)		update( top[j],1 );	}}void del(int u){
   	for(int i=dfn[u];i<=low[u];i++)	update( top[i],-1 );	}void dsu(int u,int fa,int keep){
   	for(auto v:vec[u] )		if( v!=son[u] && v!=fa )	dsu(v,u,0);	if( son[u] )	dsu( son[u],u,1 ),SON = son[u];	calc(u,fa); SON = 0;//计算以u为lca的所有答案 	if( !keep )	del(u);}int main(){
   	cin >> n;	for(int i=1;i<=n;i++)	cin >> a[i];	for(int i=1;i
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/117232970 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！