程设作业要做的题，感觉不简单，实现的有待改进，不过能满足要求
给定一棵 n 个节点的树，如果树中存在边（a,b)(b,c)(c,d)，a,b,c,d 互不相同，
并且 a 和 d 之间没有边，那么可以连一条边(a,d)，求最多能连多少条边？
输入
第一行一个整数 N，接下来 N-1 行，表示树的每一条边。
1 <= N <= 2×10
5
输出
输出一行，表示答案。
? ? ? ? ? ? ??
?代码实现:
# G. 连边问题
import copy
# 返回列表中下标为bs对应的第一个相邻的点的下标
def findfedge(nlist,bs):
i = 0
while i < len(nlist[bs]):
if nlist[bs][i] == True:
return i
i += 1
return -1
# 列表中下标为bs对应的下标ne之后第一个相邻的点的下标
def findnextedge(nlist,bs,ne):
while ne < len(nlist[bs]):
if ne == len(nlist[bs])-1:
return -1
ne += 1
if nlist[bs][ne] == True:
return ne
return -1
# 返回当前列表对应的各个点中能连成边的边数
def islinkedge(nlist):
olist = copy.deepcopy(nlist)
num = 0
a = 0
while a < len(olist): # 下标a标记（a,b)(b,c)(c,d)点a
b = findfedge(olist, a) # 下标b标记（a,b)(b,c)(c,d)点b
while True:
if b == -1:
break
c = findfedge(olist, b) # 下标c标记（a,b)(b,c)(c,d)点c
while True:
if c == a:
c = findnextedge(olist, b, c)
if c == -1:
break
d = findfedge(olist,c) # 下标d标记（a,b)(b,c)(c,d)点d
while True:
if d == b:
d = findnextedge(olist, c, d)
if d == -1:
break
if olist[a][d] == False and nlist[d][a] == False: # 判断点a和点d之间是否有边
nlist[a][d] = True
nlist[d][a] = True
num += 1
d = findnextedge(olist,c,d)
c = findnextedge(olist, b, c)
b = findnextedge(olist, a, b)
a += 1
return num
if __name__ == '__main__':
N = int(input()) # 整数N
nlist = [[False for i in range(N)] for i in range(N)] # 初始化列表，用外层列表下标对应各个点，内层列表标记点之间是否可以连边
for i in range(N-1): # 将输入的边的数据放入列表中
info = input()
info = info.strip()
sp = info.split(' ')
nlist[int(sp[0])-1][int(sp[1])-1] = True
nlist[int(sp[1])-1][int(sp[0])-1] = True
sum = 0
while True:
num = islinkedge(nlist) # 每次添加新边之后能连边的数目，第一次是未添加新边能连边的数目
if num == 0: # 如果num = 0，说明已经无法添加新边了
break
sum += num
print(sum)