供大家参考，同时求大佬思路/答案。菜成狗，做一次打击一次，大厂属实不配

1、设计无向连通图

示例：

输入：
3
0 1 1
输出：
2
1 2
1 3

图之前心存侥幸，直接跳过，下去补补。

2、多叉树染色

示例：

输入：
6
1 2
6 3
5 2
2 4
3 1
输出
BBRBBB

个人认为这个题难在多叉树的建立（做的时候一直卡在这），下面是笔试完写的，不知道能不能过。
染色思路：
用递归，染色函数solution（TreeNode root）传入一棵染色前的树，返回染色后的树。
具体实现：取到根节点root，得到root的子节点列表，然后逐个对子节点染色。若子节点的数量为偶数，则root节点必为蓝色；否则必为红色。返回染色后的树。

public class Main
{
    public static void main(String[] args)
    {
        Scanner input=new Scanner(System.in);
        int N=input.nextInt(); //节点个数
        int[][] connect=new int[N][N];//临接矩阵
        ArrayList<Integer> child_list=new ArrayList<>(); //根节点的子节点列表
        for(int i=0;i<N-1;i++)
        {
            int a=input.nextInt();
            int b=input.nextInt();
            connect[a-1][b-1]=1;
            connect[b-1][a-1]=1;
        }
        System.out.println("临接矩阵：");
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
                System.out.print(connect[i][j]+" ");
            System.out.println();
        }


        TreeNode root=new TreeNode('R',0);
        pre_build(root,connect);

        //层序遍历
        System.out.println("染色前：");
        bfs(root);


        root=solution(root);
        System.out.println("\n染色后：");
        bfs(root);

    }

    public static void pre_build(TreeNode root,int[][] connect)  //前序建树（多叉树）
    {
        if(root==null)
            return;

        int num= root.num;
        for(int i=0;i<connect.length;i++)
        {
            if(connect[num][i]==1)
            {
                root.addNode(new TreeNode('R',i));
                connect[i][num]=0;
            }
        }
        ArrayList<TreeNode> child=root.children;
        for(TreeNode o:child)
            pre_build(o,connect);
    }

    public static TreeNode solution(TreeNode root) //输入染色前的树，返回染色后的树
    {

        ArrayList<TreeNode> list=root.children;
        if(list.size()==0)
        {
            root.setColor('B');
            return root;
        }
        else
        {
            for(TreeNode o:list)
                o=solution(o);  //子节点染色

            if(list.size()%2==0) //子节点个数为偶  则根节点必为蓝色
                root.setColor('B');
            else
                root.setColor('R'); //子节点个数为奇  则根节点必为红色
            return root;

        }
    }

    public static void bfs(TreeNode root)  //层序遍历
    {
        LinkedList<TreeNode> list=new LinkedList<>();
        list.add(root);
        while(!list.isEmpty())
        {
            TreeNode tem=list.remove();
            System.out.print("("+(tem.num+1)+","+tem.color+")");
            ArrayList<TreeNode> child=tem.children;
            if(child!=null)
            {
                for(TreeNode o:child)
                    list.add(o);
            }
        }
    }

}

class TreeNode
{
    public Character color;  //颜色
    public  Integer num;  //编号
    public ArrayList<TreeNode> children=new ArrayList<>();  ///子节点列表
    public TreeNode(Character color,Integer num)
    {
        this.color=color;
        this.num=num;
    }
    public void addNode(TreeNode n)
    {
        children.add(n);
    }

    public void setColor(Character color)
    {
        this.color=color;
    }

}

3、染色种类

示例：

输入:
5
1 2 1 2 2
BRRBB

输出：
5

说明：
和为1 的取法下标：B(0), R(2)
和为2的取法下标：B(3), R(1)或B(4), R(1)
和为3的取法下标：B(0,3), R(1,2)或B(0,4), R(1,2)
（这里下标从0开始）

4、题目忘了，扫了一眼类似走迷宫，dfs之类的，没时间