#1459. C国的街道

C国的地图可以看成一个由N个点组成的树，其中每个点代表C国的一个城市，而每条边代表连接城市之间的街道。C国的街道都是平行于坐标轴的，因此每个城市最多只有4条街道与它连接，即上下左右四个方向最多只有一个城市与它通过街道所连接。现在你来到了C国旅游，你希望开车遍历尽可能多的C国的街道，不过很快你就发现如果不停地转弯地话实在太耽误时间。“转弯”的定义是在某个城市由水平方向的道路开向了垂直方向的道路或垂直方向的道路转向了水平方向的道路。所以你想找一条最长的路径使得任何一个城市最多经过一次且转弯的次数不超过K次，并且你想知道有多少条满足条件的最长的路径。