路径和

[编程题]路径和

热度指数：58 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一棵n个节点的树，每个节点都有一个价值p[i]，对于某一条路径，定义路径的价值为路径上所有点的价值在二进制下按位与的值。求所有树上路径的价值和为多少

注意，单独的一个点也算一条路径。

示例1

输入

4,[0,1,2],[1,2,3],[1,2,2,1]

输出

说明

共有5条路径对答案有贡献，(1->2)贡献为2，(0)贡献为1，(1)贡献为2，(2)贡献为2，(3)贡献为1，所以答案为2+1+2+2+1=8。

备注:

算法知识视频讲解

C++

Scarecrow928

第10个用例可能会遇到32位整数溢出问题，简易用int64

发表于 2021-08-10 20:04:59 回复(0)

小天狼星.

看了别人的代码，发现看都看不懂，然后看到有个人说连通域，突然就有思路了。

思路：

对每一位分别进行处理，假设现在是对i位处理，某两个相邻的节点的值的第i位的值都为1，则认为这两个节点是连通的，然后使用BFS遍历所有点找到所有连通域Ds-i，对于一个连通域D-i表示该连通域是在第i位的基础上找到的，则该连通域对结果的贡献为：(1<<i) * (len*(len+1)/2)，对所有连通域计算求和，即可得到最终答案。

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 点的个数
     * @param u int整型一维数组 每条边的起点
     * @param v int整型一维数组 每条边的终点
     * @param p int整型一维数组 每个点的价值
     * @return long长整型
     */
    private ArrayList<ArrayList<Integer>> connection = new ArrayList<>();
    private ArrayList<Integer> plc = new ArrayList<>();
    public long solve (int n, int[] u, int[] v, int[] p) {
        ArrayList<Integer>[] graph = get_graph(n, u, v);
        for(int i=0;i<20; i++){
            boolean[] flag = new boolean[n];
            for(int j=0; j<n; j++)
            {
                bfs(j, graph, flag, p, i);
            }
        }
        long ans = 0;
        for(int i=0; i<plc.size(); i++)
        {
            long len =connection.get(i).size();
            ans = ans + (1<<plc.get(i)) * (len*(len+1)/2);
        }
        return ans;
    }
    @SuppressWarnings("unchecked")
    public ArrayList<Integer>[] get_graph(int n, int[] u, int[] v)
    {
        ArrayList<Integer>[] graph = new ArrayList[n];
        for(int i=0; i<n; i++)
            graph[i] = new ArrayList<>();
        for(int i=0; i<u.length; i++){
            graph[u[i]].add(v[i]);
            graph[v[i]].add(u[i]);
        }
        return graph;
    }
    public void bfs(int node, ArrayList<Integer>[] graph, boolean[] flag, int[] p,int x){
        if(flag[node] || (1&(p[node]>>x))==0)
            return;
        flag[node]=true;
        ArrayList<Integer> tmp = new ArrayList<>();
        tmp.add(node);
        ArrayList<Integer> fsNode = new ArrayList<>();
        fsNode.add(node);
        while(!fsNode.isEmpty()){
            int len = fsNode.size();
            for(int i=0; i<len; i++){
                for(int j=0; j<graph[fsNode.get(0)].size(); j++){
                    int thisNode = graph[fsNode.get(0)].get(j);
                    if((1&(p[thisNode]>>x))==1 && flag[thisNode]==false){
                        flag[thisNode]=true;
                        fsNode.add(thisNode);
                        tmp.add(thisNode);
                    }
                }
                fsNode.remove(0);
            }
        }
        connection.add(new ArrayList<>(tmp));
        plc.add(x);
    }
}

发表于 2021-03-19 12:56:26 回复(0)