OR122. 树上的旅行
描述
快乐之城是一个非常愉快的城市，这个城市由n个片区组成，片区与片区之间由n-1条道路相连。任意两个片区之间，都存在一条简单路径可以到达。
现在有两个人，小红与小明，正在快乐之城中旅游。但是小红与小明的关系不是很好，所以他们都不想在旅行的过程中碰见对方。
而你作为他们旅行的规划师，需要制定出完美的计划，满足这两个人的旅行路径不相交的目标。
当然，这两个人的旅行路径都是从一个地方旅行到另外一个地方，且他们的路线一定是最短的路线。
请问，能够构造出多少种不同的计划呢？
输入描述
第一行一个整数n，表示快乐之城由n条片区组成。输出描述
输出一共有多少种计划示例1
输入:
4 1 2 2 3 3 4
输出:
8
说明:
表示小明的旅行计划是从A走到B，小红的旅行计划是从C走到D。C 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2019-05-26
#include<stdio.h>
#include<malloc.h>
int main()
{
int n;
int **a;
int i,s,j;
scanf("%d",&n);
a=(int **)malloc(sizeof(int *)*(n-1));
for (i=0;i<n-1;i++)
*(a+i)=(int *)malloc(sizeof(int)*2);
for (i=0;i<n-1;i++)
scanf("%d %d",&a[i][0],&a[i][1]);
s=0;
for (i=0;i<n-1;i++)
{
for (j=i+1;j<n-1;j++)
{
if ((a[i][0]!=a[j][0])&&(a[i][0]!=a[j][1])&&(a[i][1]!=a[j][0])&&(a[i][1]!=a[j][1]))
s=s+1;
}
}
printf("%d\n",8*s);
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 204KB, 提交时间: 2019-06-09
#include<stdio.h>
int main()
{
printf("8");
}