算法图

Question

您好，我对我的代码有疑问。我这样写。我的任务是计算连接树中两个不同节点的所有奇数路径。我尝试通过二分图来做到这一点，但是计数错误，我几乎没有比答案中更少的路径

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;
    }
}

Answer 1

考虑树

T

。

根据节点与根的距离是奇数长度还是偶数长度（可以任意选择根），将节点分成两组

A

和

B

。

以下内容成立：
在树中，两个节点

u

和

v

之间只有一条路径。
路径具有奇数长度，当且仅当

u

和

v

位于不同的集合

A

和

B

中。

因此树中奇数长度无向路径的数量 =

|A|*|B|