树中不同节点间奇数长度路径计数问题求助（二分图解法有误）

我需要统计树中连接两个不同节点的所有奇数长度路径，尝试用二分图思路实现，但计数结果比正确答案少，以下是我的Java代码：

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {

    public int solution(int[] A, int[] B){
        Graph graph = new Graph(A.length + 1);
        for (int i = 0; i < A.length; i++) {
            graph.addEdge(A[i], B[i]);
            graph.addEdge(B[i], A[i]);
        }
        int x= graph.countPath();
        return x;
    }
}

class Graph {
    ArrayList<LinkedList<Integer>> aL;
    boolean[] visited;
    int left = 0, right = 0;

    Graph(int nodes) {
        aL = new ArrayList<>();
        visited = new boolean[nodes];
        for (int i = 0; i < nodes; i++) {
            aL.add(new LinkedList<>());
        }
    }

    public void addEdge(int s, int f) {
        aL.get(s).add(f);
    }

    public void dfs(int curr, int parent, int distance){
        visited[curr] = true;
        if (distance % 2 == 1) {
            left++;
        } else {
            right++;
        }
        for (int node : aL.get(curr)) {
            if (!visited[node]) {
                dfs(node, curr, distance + 1);
            }
        }
    }

    public int countPath(){
        dfs(1, -1, 0);

        return left * (left - 1) / 2 + right * (right - 1) / 2;
    }
}

错误原因 #

二分图思路本身是对的——树是天然的二分图，节点可分为两个互不相交的集合，奇数长度路径的两个端点必然属于不同集合，偶数长度路径的端点则属于同一集合。但你的计算逻辑完全搞反了：

• left * (left - 1) / 2 + right * (right - 1) / 2 统计的是同一集合内节点对的数量，也就是所有偶数长度的路径数
• 题目需要的奇数长度路径数，应该是两个集合间节点对的数量，即 left * right

修正后的代码 #

只需修改countPath方法的返回值：

public int countPath(){
    dfs(1, -1, 0);
    return left * right;
}

补充验证方式 #

树中所有不同节点对的总数为 (left + right) * (left + right - 1) / 2，奇数路径数也可通过总节点对数减去偶数路径数得到，结果一致：

public int countPath(){
    dfs(1, -1, 0);
    int totalPairs = (left + right) * (left + right - 1) / 2;
    int evenPaths = left * (left - 1) / 2 + right * (right - 1) / 2;
    return totalPairs - evenPaths;
}

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