• 「字典树」最大异或对路径


    最大异或对路径

    原题链接:最大异或对路径

    题目大意

    给你(n)个关系,表示 (u,v) 两点间有一条边,且有边权,问异或和长度最大的路径的异或值是多少?

    题目题解

    和上一道题很像,但是需要转化一下思路,我们上一道题是两个点之间进行计算,那么这道题是不是也能这样计算呢?当然可以,但是需要转化模型,对于任意两点 (u, v) 而言,(u -> root)(v->root) 都可以将其路径的异或值都算出来,我们这里假设 (u,v) 在根节点的同一个子树上,那么这两个点到根节点的路径一定有相交的路径,如果我们想得到 (u -> v) 就可以用下面的等式 ,我们这里假设 (d[x]) 为从(x)点到根节点的路径 那么就有 (d[u] wedge d[v] wedge d[lca(u,v)] wedge d[lca(u,v)]) 又因为异或满足结合律,于是可得最终结果为 (d[u]wedge d[v]) ,于是我们就可以将每个点到根节点的结果预处理出来,最终我们就将模型转化到点上了,建个trie树,跑一遍就好

    代码如下

    //#define fre yes
    
    #include <cstdio>
    
    const int N = 100005;
    int head[N << 1], to[N << 1], ver[N << 1], edge[N];
    struct Node {
        int son[26];
    } trie[N * 30];
    
    int tot;
    void addedge(int x, int y, int z) {
        ver[tot] = y;
        edge[tot] = z;
        to[tot] = head[x];
        head[x] = tot++;
    }
    
    void dfs(int u, int fa, int sum) {
        a[u] = sum;
        for (int i = head[u]; ~i; i = to[i]) {
            int v = ver[i];
            if(v != fa) {
                dfs(v, u, sum ^ edge[i]);
            }
        }
    }
    
    int idx;
    
    void Insert(int x) {
        int rt = 0;
        for (int i = 30; i >= 0; i--) {
            int id = x >> i & 1;
            if(!trie[rt].son[id]) trie[rt].son[id] = ++idx;
            rt = trie[rt].son[id];
        } 
    }
    
    int main() {
        memset(head, -1, sizeof(head));
        static int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        
        dfs(0, -1, 0);
        
        for (int i = 1; i <= n; i++) Insert(a[i]);
    
        int ans = 0;
        for (int i = 1; i <= n; i++) ans = std::max(ans, Search(a[i]));
        
        printf("%d
    ", ans);
        return 0;
    }
    
  • 相关阅读:
    [转]oracle in 多个字段
    [转][MVC4]ASP.NET MVC4+EF5(Lambda/Linq)读取数据
    SQL Server “复制”表结构,创建_Log表及触发器
    [转]WordPress主题开发:主题初始化
    struts2请求过程源码分析
    java调优
    websocket之四:WebSocket 的鉴权授权方案
    高可用性及容灾的几个衡量指标
    Struts2返回JSON对象的方法总结
    java websocket @ServerEndpoint注解说明
  • 原文地址:https://www.cnblogs.com/Nicoppa/p/11527177.html
一二三 - 开发者的网上家园