2021RoboCom机器人开发者大赛 本科组初赛 第三题多源单权最短路径问题和单源多权最短路径问题使用floyd算法和dijkstra算法

现在给定一棵树 T，要求选择树中两个没有边相连的结点 i 和 j，使得将无向边 (i,j) 加进 T 后能够构成二分图。你的任务是计算满足这个要求的选择方案有多少种。输入格式:输入第一行给出一个正整数 N (2≤N≤1e6)，表示树中结点的个数。接下来 N−1 行，每行给出树中一条边的两端结点编号，以空格分隔。结点编号从 1 开始。题目保证输入给出的是一棵树中所有的边。输出格式:在一行中输出方案数