Kattis题目《Marbles on a Tree》运行时异常排查求助

我参考UVa 10672《Marbles on a Tree》的解法实现Kattis《marblestree》问题，这是一道树结构+类DFS贪心策略的图论题。代码能通过样例，但第二个测试用例触发运行时异常，Kattis未提供具体提示。已排除内存超限和超时，推测异常出在que.size() > 0的while循环中，但无法定位具体位置。

原代码：

import java.util.*;
import java.io.*;

public class marblestree
{
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static ArrayList<Integer> values = new ArrayList<>();
    public static ArrayList<Integer> leaves = new ArrayList<>();
    
    public static void main(String args[]) throws IOException
    {
      Scanner in = new Scanner(System.in);
      
      int n = 1;
      while (n > 0)
      {
         n = in.nextInt();
         if (n == 0)
            break;
         for (int i = 0; i < n; i++)
         {
            adjList.add(new ArrayList<Integer>());
         }
         for (int j = 0; j < n; j++)
         {
            in.nextInt();
            values.add(in.nextInt());
            int adjNum = in.nextInt();
            for (int m = 0; m < adjNum; m++)
            {
               adjList.get(in.nextInt() - 1).add(j);
            }
            if (adjNum == 0)
               leaves.add(j);
         }
         
         //handle case
         LinkedList<Integer> que = new LinkedList<>();
         for (Integer y : leaves)
         {
            que.add(y);
         }
         
         int moves = 0;
         
         adjList.get(0).add(0);
         
         while (que.size() > 0)
         {
            int now = que.poll();
            if (now != 0)
            {
               if (adjList.get(now).get(0) > 0 && !que.contains(adjList.get(now).get(0)))
                  que.add(adjList.get(now).get(0));
               moves += Math.abs(values.get(now) - 1);
               values.set(adjList.get(now).get(0), values.get(adjList.get(now).get(0)) + (values.get(now) - 1));
               values.set(now, 1);
            }
         }
         
         System.out.println(moves);
         
         adjList = new ArrayList<>();
         values = new ArrayList<>();
         leaves = new ArrayList<>();

      }
    }
}

核心错误分析 #

1. 输入与数据结构错位

   • values列表按输入顺序添加元素，而非节点编号顺序，导致后续通过索引访问节点大理石数时完全错位。
   • 邻接表构建逻辑错误：将当前输入节点的索引j添加到邻居节点的邻接表中，而非将邻居节点索引添加到当前节点的邻接表，导致树的父子/邻居关系完全混乱。

2. 叶子节点判断错误
   树中除单节点外，叶子节点的邻居数为1（仅与父节点相连），但原代码判断adjNum == 0才视为叶子，导致错误地将非叶子节点加入队列，后续处理时邻接表为空，调用get(0)触发IndexOutOfBoundsException。

3. 无意义的根节点自环
   adjList.get(0).add(0)强行给根节点添加自环，可能导致循环处理根节点，引发逻辑错误。

修正后的代码 #

import java.util.*;
import java.io.*;

public class marblestree
{
    public static void main(String args[]) throws IOException
    {
        Scanner in = new Scanner(System.in);
        
        int n;
        while ((n = in.nextInt()) != 0)
        {
            ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
            for (int i = 0; i < n; i++)
            {
                adjList.add(new ArrayList<>());
            }
            
            ArrayList<Integer> values = new ArrayList<>(Collections.nCopies(n, 0));
            int[] degree = new int[n];
            
            for (int i = 0; i < n; i++)
            {
                int u = in.nextInt() - 1; // 转为0-based索引
                int m = in.nextInt();
                int k = in.nextInt();
                values.set(u, m);
                
                for (int j = 0; j < k; j++)
                {
                    int v = in.nextInt() - 1;
                    adjList.get(u).add(v);
                    adjList.get(v).add(u);
                    degree[u]++;
                    degree[v]++;
                }
            }
            
            LinkedList<Integer> que = new LinkedList<>();
            // 初始化队列：加入所有度数为1的非根节点（根是0）
            for (int i = 0; i < n; i++)
            {
                if (i != 0 && degree[i] == 1)
                {
                    que.add(i);
                }
            }
            
            int moves = 0;
            
            while (!que.isEmpty())
            {
                int now = que.poll();
                if (degree[now] == 0) continue; // 已处理过的节点跳过
                
                // 找到父节点：邻居中度数>0的节点（未被处理）
                int parent = -1;
                for (int neighbor : adjList.get(now))
                {
                    if (degree[neighbor] > 0)
                    {
                        parent = neighbor;
                        break;
                    }
                }
                
                // 计算移动次数并更新大理石数量
                moves += Math.abs(values.get(now) - 1);
                values.set(parent, values.get(parent) + values.get(now) - 1);
                
                // 标记当前节点已处理，更新父节点度数
                degree[now] = 0;
                degree[parent]--;
                
                // 如果父节点变为叶子（非根），加入队列
                if (parent != 0 && degree[parent] == 1)
                {
                    que.add(parent);
                }
            }
            
            System.out.println(moves);
        }
        in.close();
    }
}

修正说明 #

1. 输入处理修正

   • 将节点编号转为0-based索引，values按节点索引直接赋值，确保数据与节点一一对应。
   • 正确构建双向邻接表，并记录每个节点的度数，用于后续叶子节点判断与拓扑排序。

2. 叶子节点与队列初始化
   以度数为1的非根节点作为初始叶子节点加入队列，符合树的叶子定义。

3. 循环逻辑修正

   • 遍历当前节点的邻居找到未处理的父节点，避免依赖错误的邻接表顺序。
   • 处理完节点后标记其度数为0，更新父节点度数，当父节点变为叶子时加入队列，确保按从下到上的顺序处理（类后序遍历）。

内容的提问来源于stack exchange，提问作者Ramsey Alsheikh