第六届CCPC长春站正式赛-F

第六届CCPC长春站正式赛-F

十一月 10, 2020

F. Strange Memory

  • ##题意

给出一个n个点n-1条边的一颗树 (n<=1e5)

对于一个点$i$有值$a_i$ (1<=ai<=1e6)

现在要求 $∑{i=1}^n∑{j=i+1}^n [a_i⊕a_j=a_{lca(i,j)}]×(i⊕j). $

即对于任何满足$[a_i⊕a_j=a_{lca(i,j)}]​$ 的点对(i,j) 的下标异或值求和

  • 题解

参考题解

dsu on tree

解决这个问题需要解决以下几个问题：

  • 如何找到符合$[a_i⊕a_j=a_{lca(i,j)}]$ 的点对
  • 如何统计答案

对于第一个问题 我们可以枚举一个点作为Lca 同时枚举一个它(Lca)的子节点作为$i$

那么只需要寻找以它(Lca)为根的子节点中是否存在一个$a_j=a_{Lca} ⊕ a_{i}$

对于第二个问题

朴素的想法是 我们用一个容器(比如map<int,vector >,关键字是点值,映射值是该点值的所有点下标值)

存某个点作为Lca的一支子树中 值为$a_j$的点的下标

于是对于这个Lca需要枚举另一支子树中的 $a_i$

再枚举遍历容器中值为($a_{Lca} ⊕ a_{i}$) 的所有下标值 ans+=i⊕j

然后将$a_i$所在子树插入到容器中传递到上一层

这么做导致 我们不得不遍历子树中的$a_i$ 和$a_j$ 来获取下标的异或值

实际上就是在暴力枚举点对(i,j)没有任何优化

###于是要着手如何更快速地统计答案；

首先意识到i⊕j 可以拆分成按位异或

那么当且仅当 符合$[a_i⊕a_j=a_{lca(i,j)}]$ 的点对(i,j) 在同一位二进制下相异

最终答案才会有这一位二进制的贡献

比如点对(3,6) 二进制下(011,110) 3^6=5 即第0位和第2位相异的二进制位会对最终答案产生贡献

如果我们知道Lca下某个子树集合内 $a_j$的所有下标每位二进制为0/1的个数有几个

那么我们枚举$a_i$ 时可以直接算 对于需要的$a_j=a_i ⊕a_{Lca}$ 中所有二进制位 为0/1的下标有多少个

就可以直接求得某位二进制下 i⊕j对答案产生的贡献

于是设计一个三维数组：$BitCnt(val,bit,0/1)$

表示在某Lca的子树下点值为val的 下标 符合第bit位 为0/1 共有多少个

子树中$a_j$被作为一个集合统计在$BitCnt$中 就不需要逐个枚举$a_j$ 而改为枚举二进制位了

这么做的目的也是为了方便使用树上启发式合并

  • 什么是dsu on tree？

    它是用来解决一类树上询问问题，一般这种问题有两个特征

    1、只有对子树的询问

    2、没有修改

这个问题中需要更新维护每个点作为Lca时的BitCnt 也就是对子树集合信息的询问

对于dsu on tree的算法流程大概是：

首先需要预处理重链剖分(FInd_BigSon) 得到对于每个父节点 它子节点相对而言的重子树

什么叫消除轻儿子产生的影响而保留重儿子？

以本题为例 我们需要维护$BitCnt$ 是以某个点作为Lca的子树集合信息

而他作为全局变量 它在递归中被以不同点作为root的子树集合信息更新

而我们在求点对(i,j)时 是同一个点Lca 下的子树集合中 的信息

如图 (红圈表示以其父节点下所有子节点相较而言的重子树)

对于Lca=5的子树集合 i=6 我只需要从5的其他支子树的BitCnt集合中得到

而递归过程会将所有其他子树集合信息一并更新到BitCnt这个全局变量中 导致对于i=6

我所找到对应的j 就不仅限于Lca=5的子树中的信息了

对于启发式合并 每次将轻子树集合的信息并入到重子树中

抹除轻子树的信息 然后将重子树传递到上一层递归 (返回到父节点)

若上一层的父节点不再是重子树 那么抹除它们的信息 将他们视为轻子树集合

重新并入到同一层中的重子树中

这也体现了启发式合并的核心思想：

将小集合信息并入到大集合信息使得整体复杂度下降到nlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
//#define P pair<ll,ll>
const int Max=1e5+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;

//#define __DEBUG__
#ifdef __DEBUG__
#define DeBug(format, ...)
{
    fprintf(stdout, "[%s:%d] " format "",
    __FUNCTION__ , __LINE__, ##__VA_ARGS__);
}
#else
#define DeBug(format,...)
#endif
/*
6
4 2 1 6 6 5
1 2
2 3
1 4
4 5
4 6
*/

int BitCnt[(1<<20)+100][30][2];
/// val,bit,1/0
vector<int>mp[Max];
queue<int>SmallSon;
int val[Max];
ll ans=0;
int sz[Max],BigSon[Max];
bool vis[Max];

void Find_BigSon(int now,int fa){
    sz[now]=1;
    for(auto to:mp[now]){
        if(to==fa)continue;
        Find_BigSon(to,now);
        sz[now]+=sz[to];
    }
    if(sz[now]>sz[BigSon[fa]])BigSon[fa]=now;
}

inline void Updata(int id,int add){
    DeBug("id:%d add:%d\n",id,add);
    for(int i=0;i<=20;i++)BitCnt[val[id]][i][!((id>>i)&1)]+=add;
}

void Delete(int now,int fa){
    Updata(now,-1);
    for(auto to:mp[now]){
        if(to==fa)continue;
        Delete(to,now);
    }
}

void Deal(int now,int fa,int lca){
    //DeBug("now:%d\n",now);
    SmallSon.push(now);
    int need=val[now]^val[lca];
    for(int i=0;i<=20;i++){
        //DeBug("need:%d now:%d add:%d\n",need,now,BitCnt[need][i][(now>>i)&1])
        ans+=BitCnt[need][i][(now>>i)&1]*(1<<i);
    }
    for(auto to:mp[now]){
        if(to==fa)continue;
        Deal(to,now,lca);
    }
}

void dfs(int now,int fa,bool keep){
    ///递归处理轻子树
    for(auto to:mp[now]){
        if(to==fa||to==BigSon[now])continue;
        dfs(to,now,0);
    }
    ///递归处理重子树
    if(BigSon[now])dfs(BigSon[now],now,1);
    ///将轻子树并入到重子树中并更新答案
    vis[BigSon[now]]=1;
    Updata(now,1);
    for(auto to:mp[now]){
        if(to==fa||vis[to])continue;
        //DeBug("in\n");
        Deal(to,now,now);
        ///暴力枚举轻子树的点i
        ///此时BitCnt中存的是重子树中所需的j的信息
        while(!SmallSon.empty()){
            int temp=SmallSon.front();
            SmallSon.pop();
            Updata(temp,1);
        }
    }
    vis[BigSon[now]]=0;
    ///删除轻子数对全局BitCnt的影响
    if(!keep)Delete(now,fa);
}

int main(void){
    //Turnoff;
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>val[i];
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    Find_BigSon(1,0);
    dfs(1,0,1);
    //for(int i=1;i<=n;i++)DeBug("%d %d\n",i,BigSon[i]);
    cout<<ans<<endl;
}