icontofig | 发布于 2020-02-11 17:05:57 | 阅读量 313 | Trie
发布于 2020-02-11 17:05:57 | Trie

题目大意

有n个节点的有根树,根为1,每条边有权值,点对(u,v)的路径长度为从u到v路径上所有权值的异或值,认为点对(u,v)与(v,u)表示两个路径,总共有n2个点对路径(自己到自己也算一个),求问其中路径长度第k小的路径长为多少。

题解

n的范围是很大的,不可能通过枚举计算。

两点(u,v)之间的路径长度,可以通过lca转化为:

(u,lca) xor (v,lca) = (u,lca) xor (lca,root) xor(lca,root) xor (v,lca) = (u,root) xor (v,root);

所以可以将每个点到根节点的路径异或长度预处理出来,之后再进行下面的操作。

建立一个01Trie,我们可以有办法求得路径异或长度不超过某个值val的路径数目。

对于当前位bit,我们去检查小于之前已经决定的答案ans加1<<bit的值的个数。也即当前的二进制位上的数为0的个数。

如果这个个数size小于k,说明答案应该是大于等于ans + (1<<bit)的,于是就决定当前的二进制位为1,k -= size,进入当前层表示为1的子树内再向下搜寻。

否则就直接进入当前层表示为0的子树内再向下搜寻。

整个搜寻答案的过程是O(62·n)的。加二分实际上是没意义的。

最后的一个问题就是,空间明显不允许我们开这样一个完整的Trie,所以需要动态建立每一层的Trie节点,用到什么建什么,不用的不管,搜寻下一层的时候要将上一层的节点表示清空。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k;
int id;
const int maxn = 1e6+5;
ll v[maxn];
int pre[maxn];
int tot = 0;
ll siz[maxn];
int son[maxn][2];
int a[maxn],b[maxn];
void init(){
    for(int i = 1;i <= n;++i)
        son[i][0] = son[i][1] = 0,siz[i] = 0;
    tot = 0;
}
int new_tag(int now,int ch){
    if(!son[now][ch])
        son[now][ch] = ++tot;
    return son[now][ch];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    cin >> k;
    for(int i = 2;i <= n;++i){
        cin >> pre[i];
        cin >> v[i];
        v[i] ^= v[pre[i]];
    }
    for(int i = 1;i <= n;++i){
        a[i] = 1;
        b[i] = 1;
    }
    ll ans = 0;
    for(int i = 62;~i;i--){
        ll sz = 0;
        init();
        int ch = 0;
        for(int j = 1;j <= n;++j){
            siz[a[j] = new_tag(a[j],(v[j] >> i) & 1)]++;
        }
        for(int j = 1;j <= n;++j){
            int t = son[b[j]][(v[j]>>i)&1];
            sz += siz[t];
        }
        if(sz < k){
            k -= sz;
            ch = 1;
            ans += (1ll<<i);
        }
        for(int j = 1;j <= n;++j){
            b[j] = son[b[j]][((v[j]>>i)&1)^ch];
        }
    }
    cout << ans << endl;
    return 0;
}



内容更新于: 2020-02-11 20:13:29
链接地址: http://blog.leanote.com/post/icontofig/c87ea40e10da

上一篇: CodeForces 710F. String Set Queries 模拟二进制堆启发式合并的AC自动机合并

下一篇: CodeForces - 484E Sign on Fence 二分+主席树

313 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航