网站首页改版方案南通市建设局网站

原题链接：

题目描述

Foxity和他的好友们相约去爬山，但是他们每个人都来到了不同的山脚下。整个山的结构类似一棵 "树"，有很多的观光节点通过一条条山道连接起来。

在图论中，树是一种无向图，其中任意两个顶点之间存在唯一一条路径。或者说，只要没有回路的连通图就是树。这个问题中，我们将山顶视作树的根节点，而山脚视为树的叶节点，上山的每一条路可以视作树的一条边。

由于上山的道路年久失修，每条道路在同一时刻只能容纳一个人，而通过一条道路需要花费 111 时间。

现在他们分散在各个山脚（每个山脚恰好有一个人），现在他们想要知道最快的情况下，从现在到最后一个人登上山顶总共要花费多久的时间。

输入描述:

第一行一个整数 n(1≤n≤1000)n(1 \le n \le 1000)n(1≤n≤1000),表示总共节点的数量。接下来 n−1n-1n−1 行，每行两个整数，分别是 xi,yi(1≤xi,yi≤n)x_i,y_i(1 \le x_i,y_i \le n)xi​,yi​(1≤xi​,yi​≤n)，表示有一条路连接 xix_ixi​ 号点 和 yiy_iyi​ 号点，其中 111 号点即为山顶，保证给定的图是一棵树。

输出描述:

输出一行一个数，表示所有人都到齐的最少时间。

示例1

输入

复制3 1 2 1 3

3
1 2
1 3

输出

复制1

1

示例2

输入

复制4 1 2 2 3 2 4

4
1 2
2 3
2 4

输出

复制3

3

思路：

1，这个题真的没什么思路

2，要求每次一条路只能走一人，所有人走到1节点的最短时间

3，这个题最难的是，单个节点记录数量，dfs深度搜索，递归的书写

代码：

int num[1100];
vector<int>g[1100];
void dfs(int z,int fa){for(int i=0;i<g[z].size();++i){int y=g[z][i];if(y==fa)continue;//防止重复遍历if(num[y]){//模拟走的过程num[z]++;num[y]--;}dfs(y,z);//遍历子节点}
}
signed main(){//dfs模拟每一秒的动作int n;cin>>n;rep(i,1,n-1){int x,y;cin>>x>>y;g[x].emplace_back(y);//无向图g[y].emplace_back(x);}int sum=0;rep(i,2,n){if(g[i].size()==1)sum++,num[i]=1;//记录单个节点的}int ans=0;while(num[1]!=sum){//模拟每一秒，在一条路上能走则走dfs(1,1);ans++;}cout<<ans<<'\n';return 0;
}