hallo_worlda level
获赞
44
粉丝
2
关注
7
看过 TA
386
北京交通大学
2024
Java
IP属地:北京
暂未填写个人简介
私信
关注
民生银行 软件工程师 n*(14-16)
0 点赞 评论 收藏
转发
华为 数通 1.7*(14-16) 其他
0 点赞 评论 收藏
转发
0 点赞 评论 收藏
转发
#笔试复盘##百度笔试#原题啊,兄弟么,第三题就是A不了,超时,哪位好兄弟帮忙看看import java.util.*;public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        sc.nextLine();        String color=sc.nextLine();        List<List<Integer>> edge=new ArrayList<>();        edge.add(new ArrayList<>());        while(sc.hasNextLine()){            int a=sc.nextInt();            int b=sc.nextInt();            sc.nextLine();            while(a>=edge.size()) edge.add(new ArrayList<>());            while(b>=edge.size()) edge.add(new ArrayList<>());            if(a==b) continue;            edge.get(a).add(b);            edge.get(b).add(a);        }        allBlock=new int[n+1];        dfs1(1,0,edge,color);        dfs2(1,0,edge,color);        System.out.println(res);    }    static int res=0;    public static void dfs2(int cur,int parent,List<List<Integer>> edge,String color){        for(int i=0;i<edge.get(cur).size();i++){            int next=edge.get(cur).get(i);            if(next==parent) continue;            dfs2(next,cur,edge,color);            if(color.charAt(cur-1)==color.charAt(next-1)){                res+=Math.abs(allBlock[next]-(allBlock[1]-allBlock[next]+1));            }else{                res+=Math.abs(allBlock[next]-(allBlock[1]-allBlock[next]));            }        }    }    static int allBlock[];    public static int dfs1(int cur,int parent,List<List<Integer>> edge,String color){        int curblock=1;        for(int i=0;i<edge.get(cur).size();i++){            int next=edge.get(cur).get(i);            if(next==parent) continue;            allBlock[cur]+=dfs1(next,cur,edge,color);            if(color.charAt(cur-1)==color.charAt(next-1)) allBlock[cur]--;        }        return allBlock[cur];    }}
投递百度等公司10个岗位
0 点赞 评论 收藏
转发
牛客网
牛客企业服务