佛山网站seo,下载app安装,怎样做无水印视频网站,怎样做网站文件验证题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/157/B 来源#xff1a;牛客网
题目描述 传说#xff0c;凤凰是百鸟之王。有一天#xff0c;凤凰要召开百鸟大会#xff0c;百鸟国是一个由n个节点组成的树#xff0c;每个节点有一只鸟#xff0…题干
链接https://ac.nowcoder.com/acm/contest/157/B 来源牛客网
题目描述 传说凤凰是百鸟之王。有一天凤凰要召开百鸟大会百鸟国是一个由n个节点组成的树每个节点有一只鸟开会的节点定在1号节点。每只鸟可以花费1s通过一条边由于每根树枝(边)的载重有限只允许一只鸟同时通过。作为会议的策划师HtBest想知道百鸟国的所有鸟在1点集合最少需要多少秒。
输入描述:
第一行有一个正整数n表示百鸟国节点个数。
接下来n-1行第i行两个正整数ai,bi用空格隔开表示树上节点ai,bi之间有一条边。
输出描述:
第一行一个整数表示集合最少需要的时间。
示例1
输入
复制
3
1 2
2 3
输出
复制
2
示例2
输入
复制
3
1 2
1 3
输出
复制
1
示例3
输入
复制
4
1 2
2 3
2 4输出
复制
3
备注:
对于100%的测试数据
1 ≤ n ≤ 1000000
数据量较大注意使用更快的输入输出方式。
解题报告 这题用dfs会超时我也不知道为什么。O(n)的复杂度。。。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e6 5;
int n,m;
vectorint vv[MAX];
int dfs(int cur,int rt) {int res 1;for(auto v : vv[cur]) {if(v rt) continue;res dfs(v,cur);}return res;
}
inline int read() {char ch getchar(); int x 0, f 1;while(ch 0 || ch 9) {if(ch -) f -1;ch getchar();} while(0 ch ch 9) {x x * 10 ch - 0;ch getchar();} return x * f;
}
int f[MAX],num[MAX];
int getf(int v) {return f[v] v ? v : f[v] getf(f[v]);
}
bool merge(int u,int v) {int t1 getf(u);int t2 getf(v);if(t1 t2) {return 1;}else {f[t2] t1;num[t1] num[t2];return 0 ;}
}
int main()
{cinn;for(int i 1; in; i) f[i] i,num[i]1;for(int a,b,i 1; in-1; i) {aread();bread();if(a!1 b!1) merge(a,b);}int ans 0 ;for(int i 1; in; i) {ans max(ans,num[getf(i)]);}cout ans;return 0;
}
TLE代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e6 5;
int n,m;
vectorint vv[MAX];
int dfs(int cur,int rt) {int res 1;for(auto v : vv[cur]) {if(v rt) continue;res dfs(v,cur);}return res;
}
int main()
{cinn;for(int a,b,i 1; in-1; i) {scanf(%d%d,a,b);vv[a].pb(b);vv[b].pb(a);}int ans 0 ;for(auto v : vv[1]) {ans max(ans,dfs(v,1));}cout ans;return 0;
}
