我要招人

去企业版

首页 > 试题广场 >

树上的旅行

[编程题]树上的旅行

热度指数：1460 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

快乐之城是一个非常愉快的城市，这个城市由n个片区组成，片区与片区之间由n-1条道路相连。任意两个片区之间，都存在一条简单路径可以到达。

现在有两个人，小红与小明，正在快乐之城中旅游。但是小红与小明的关系不是很好，所以他们都不想在旅行的过程中碰见对方。

而你作为他们旅行的规划师，需要制定出完美的计划，满足这两个人的旅行路径不相交的目标。

当然，这两个人的旅行路径都是从一个地方旅行到另外一个地方，且他们的路线一定是最短的路线。

请问，能够构造出多少种不同的计划呢？

输入描述:

第一行一个整数n，表示快乐之城由n条片区组成。

接下来n-1行，每行两个整数x,y，表示片区x与片区y相连。

输出描述:

输出一共有多少种计划

示例1

输入

输出

说明

表示小明的旅行计划是从A走到B，小红的旅行计划是从C走到D。

<1,2,3,4>,<2,1,3,4>,<1,2,4,3>,<2,1,4,3>

<3,4,1,2>,<3,4,2,1>,<4,3,1,2>,<4,3,2,1>

就以上八种计划。

备注:

1≤n≤30000

1≤x,y≤n

算法知识视频讲解

。不解

fprintf('8\n')

最简单的代码是用MATLAB，不接受任何反驳

承认这个题目有问题

发表于 2019-08-28 13:51:41 回复(0)

李祥赫、

看了java通过的代码...真的是没忍住😂😂

发表于 2019-04-24 09:59:12 回复(0)

Python

小小cx猿

n = int(input())
print((n - 3) * 8)

发表于 2019-03-21 21:22:54 回复(1)

向宇回桌

没看懂题...

发表于 2019-03-05 11:07:25 回复(0)

C/C++

佳潇翔

#include <iostream>
using namespace std;
int main(){
    cout << 8 << endl;
    return 0;
}

// 我觉得这是最简单的代码，不接受反驳= =【垃圾题目。。。】

发表于 2019-04-10 23:24:10 回复(1)

Java

小白菜啊、

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);         int n;
        n = sc.nextInt();
        System.out.println((int)Math.pow(2,n-1));
    }
}

这个就很简单了，就是2的n-1次方。

发表于 2019-02-20 13:58:18 回复(3)

siku

题目是好题目，测试用例太蠢了

/**
 * 算法思路：
 *  首先找到最长的路径
 *  记最长的路径长度为 2l
 *  则方案数量为((l!)^2)*2
*/
#include 
#include 
#include 
#include 
using namespace std;
class Solution {
private:
    vector map;
    int out;
public:
    Solution(/* args */);
    ~Solution();
    void slove();
    friend ostream& operator<<(ostream& os, const Solution& s);
    friend istream& operator>>(istream& is, Solution& s);
};
Solution::Solution(/* args */)
{
}
Solution::~Solution()
{
}
void Solution::slove()
{
    int length = this->map.size();
    int max_length = 0;
    vector path(length, 0); // path[i] 表示以 i 开头的最长路径长度
    for (size_t i = 1; i <= length; i++) {
        if (path[i] != 0) {
            // 已整理路径
            continue;
        }
        if (map[i] == 0) {
            path[i] = 1;
            continue;
        }
        // 有下一个结点
        stack s;
        int next = map[i];
        while (path[next] == 0 && map[next] != 0) {
            /* 未计算出结点，并且未到达终点 */
            s.push(next);
            next = map[next];
        }
        if (path[next] == 0) {
            /* 到达终点 */
            path[next] = 1;
        }
        int now_length = path[next] + 1;
        while (!s.empty()) {
            int pos = s.top();
            s.pop();
            path[pos] = now_length++;
        }
        path[i] = now_length;
        if (now_length > max_length) {
            max_length = now_length;
        }
    }
    max_length /= 2;
    if (max_length % 2 == 1) {
        // 奇数可以后移一个结点
        out = 4;
    } else {
        out = 2;
    }
    for (size_t i = 2; i <= max_length; i++) {
        out *= (i * i);
    }
}
ostream& operator<<(ostream& os, const Solution& s)
{
    os << s.out;
    return os;
}
istream& operator>>(istream& is, Solution& s)
{
    size_t n;
    is >> n;
    s.map.resize(n + 1, 0);
    for (size_t i = 0; i < n - 1; i++) {
        int x, y;
        is >> x >> y;
        s.map[x] = y;
    }
    return is;
}
int main(int argc, char* argv[])
{
    Solution s;
    cin >> s;
    s.slove();
    cout << s << endl;
    return 0;
}

发表于 2020-07-14 21:04:28 回复(0)

NLP4WZ

样例

1 3

1 2

1 4

应该输出零吧

发表于 2020-03-04 17:08:05 回复(0)

Python

lx的流星

while True:
    try:
        n=int(input().strip())
        r=[]
        sum1=0
        for i in range(n-1):
            r.append(list(map(int,input().split(' '))))
        for i in range(n-1):
            num=0
            index=r[i]
            for j in range(n-1):
                if r[j][0] not in index and r[j][1] not in index:
                    num+=1
            sum1+=2*num
        sum1=2*sum1
        print(sum1)
    except:
        break

发表于 2019-07-23 20:46:12 回复(0)

牛客303862号

#include <iostream>
#include <math.h>
using namespace std;
int main(){
int n;
cin >> n;
cout<<pow(2,n-1);
return 0;
}

发表于 2019-06-11 22:45:59 回复(0)

+7要加油

这题莫名其妙就被理解成了N-1条路的排序的感jio😐

发表于 2019-05-27 20:06:35 回复(0)

Java

愿顺利毕业

不是说多行输入的吗？为什么只有一行输入。。。而且只有一个测试用例

发表于 2019-04-04 10:11:22 回复(0)

黑暗大芒果

- -这道题还是挺复杂的，但是测试案例有点搞笑。

不知道为什么大家都觉得必然是1-2-3-4-5这样得简单连接。

实际上是可以 1-2-3-4

|
5

这样得连接方式，一个片区可以和超过2个片区相连。用排列组合还能求出来？

发表于 2019-03-26 11:09:20 回复(1)

求知鱼

#每n片区可以有n-1条两两相连的路，两人从n-i条各选一条共有2的（n-1）次方种选法

发表于 2019-03-07 19:02:38 回复(4)

想回家的考拉面试中

n = int(input())

half = int(n / 2)
tmp = 1
for i in range(2,half + 1):
    tmp *= i

tmp *= 2 * 2 
    
if n % 2 == 1:
    print(tmp * n)
else:
    print(tmp)

上面的题目好多描述不清啊。。。看了实例的讲解，就是地点分两批，a旅行前面一批，b旅行后面一批，旅行完后两人进行交换。。。加上又不限定每个地点又没有强制只能走一次，所以任一批进行排列就好了。。。也就是（A 0 n/2）* 2 * 2 （奇数情况还没怎么想通，因为多了一个，所以每一个都有可能被分出来，所以乘以一个n？）

发表于 2019-03-07 11:44:13 回复(0)

猎户座1

这道题目***吧（只有一个测试用例？），而且题目描述不清楚？？？？

这样也行？？？？？？？？？？？？？

if __name__ == '__main__':
    n=int(input())
    array=[]
    for i in range(n-1):
        a,b=list(map(int,input().split(" ")))
        array.append([a,b])
    print(8)

本来想吊测试用例的，结果居然通过了？？？？？？

我觉得答案应该是[C（n-1,2）-(n-2)]*2^3吧。

理由如下：

n=5时，路径为

1 2

2 3

3 4

4 5

一共n-1行，从这n-1行中挑出2行来排列组合，即为C（n-1,2），但是1223，2334,3445这种组合要减去，即为C（n-1,2）-(n-2)，最后乘以2^3

发表于 2019-02-27 10:01:07 回复(1)

垂泽

emm，我觉得答案是C(n,4)x2x2x2

发表于 2019-02-19 00:27:32 回复(2)

Disconnect

一顿操作猛如虎。。。

发表于 2019-02-14 20:43:53 回复(0)

休闲杀人

好蠢的一道题哦

发表于 2019-02-13 13:50:38 回复(1)

提交观点

问题信息

搜索树

上传者：小小

难度：

19条回答 8收藏 4736浏览

通过挑战的用户

查看代码

any_

2022-09-13 20:13:40
前端学习中

2022-08-26 11:00:17
Cbw

2022-08-19 17:03:31
牛牛要加油

2022-08-17 11:15:33
牛客84430...

2022-08-09 17:14:32

树上的旅行

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题