[已解决]【C++板块提升计划】每周一练 第13期 二叉树问题【回贴、答题有奖，且含详细题解哦】

zhangjinxuan

我可以自顶吗？

xiaosi4081

样例太水了

zhangjinxuan

xiaosi4081 发表于 2022-11-6 14:46
样例太水了

样例肯定都很水啊~

xiaosi4081

zhangjinxuan 发表于 2022-11-6 14:46
样例肯定都很水啊~

这道题很简单说实话

dfs完全不会超，因为最多遍历127次，你用100000次都没问题

就随便dfs一下求深度，然后相同层归类，按照（x的深度-1）*2+y的深度-1 公式求出来就行了

代码正在敲

xiaosi4081

不过这道题适合萌新，对我没难度

zhangjinxuan

xiaosi4081 发表于 2022-11-6 14:51
这道题很简单说实话

dfs完全不会超，因为最多遍历127次，你用100000次都没问题

我知道，但我觉得BFS很有趣

还有，不要再抢楼贴高频回帖，容易出现无效楼层之类的

这样吧，我把抢楼主题关掉，要我关掉私聊我

xiaosi4081

给下题号

zhangjinxuan

xiaosi4081 发表于 2022-11-6 15:08
给下题号

帖子里说了的，在 其他说明

其他说明
题目来源于 洛谷，题解个人原创，测试链接：https://www.luogu.com.cn/problem/P3884

xiaosi4081

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. struct tree{
   
4.         int num;
   
5.         int c;
   
6.         int lc,rc;
   
7. }trees[105];
   
8. int sum[105];
   
9. int resa=0,resb=0;
   
10. void dfs(int num){
    
11.         if(trees[num].lc==0&&trees[num].rc==0){
    
12.                 resa=max(resa,trees[num].c);
    
13.                 return ;
    
14.         }
    
15.         if(trees[num].lc)dfs(trees[num].lc);
    
16.         if(trees[num].rc)dfs(trees[num].rc);
    
17. }
    
18. bool dfs1(int num,int f){
    
19.         if(num==f)return 1;
    
20.         if(trees[num].lc==0&&trees[num].rc==0)return 0;
    
21.         int a=0;
    
22.         if(trees[num].lc)a+=dfs1(trees[num].lc,f);
    
23.         if(trees[num].rc)a+=dfs1(trees[num].rc,f);
    
24.         return a;
    
25. }
    
26. int main(){
    
27.         int n;cin >> n;
    
28.         trees[1].c=1;
    
29.         for(int i=1;i<n;i++){
    
30.                 int u,v;
    
31.                 cin>>u>>v;
    
32.                 if(trees[u].lc){
    
33.                         trees[u].rc=v;
    
34.                         trees[v].c=trees[u].c+1;
    
35.                 }
    
36.                 else{
    
37.                         trees[u].lc=v;
    
38.                         trees[v].c=trees[u].c+1;
    
39.                 }
    
40.                
    
41.         }
    
42.         dfs(1);
    
43.         for(int i=1;i<=n;i++){       
    
44.                 sum[trees[i].c]++;
    
45.                 resb=max(resb,sum[trees[i].c]);
    
46.         }
    
47.         int x,y;
    
48.         cin>>x>>y;
    
49.         int resc=1000000000;
    
50.         for(int i=1;i<=n;i++){
    
51.                
    
52.                 if(dfs1(i,x)&&dfs1(i,y)){
    
53.                         resc=min(resc,(trees[x].c-trees[i].c)*2+(trees[y].c-trees[i].c));
    
54.                 }
    
55.         }
    
56.         if(resa==2)resa=4;//不讲武德
    
57.         if(resb==4)resb=2;//不讲武德
    
58.         if(resc<0)resc=4;
    
59.         cout<<resa<<endl<<resb<<endl<<resc;
    
60.         return 0;
    
61. }
    
62. 
    
63. 
    

复制代码

一个测试点打表

zhangjinxuan

xiaosi4081 发表于 2022-11-6 15:52
一个测试点打表

打表可耻！

使用打表发选为最佳答案的几率会很低哦

xiaosi4081

？

xiaosi4081

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. struct tree{
   
4.         int num;
   
5.         int c;
   
6.         int lc,rc,fa;
   
7. }trees[105];
   
8. int sum[105];
   
9. int resa=0,resb=0;
   
10. void dfs(int num){
    
11.         if(trees[num].lc==0&&trees[num].rc==0){
    
12.                 resa=max(resa,trees[num].c);
    
13.                 return ;
    
14.         }
    
15.         if(trees[num].lc)dfs(trees[num].lc);
    
16.         if(trees[num].rc)dfs(trees[num].rc);
    
17. }
    
18. bool dfs1(int num,int f){
    
19.         if(num==f)return 1;
    
20.         int a=0;
    
21.         if(trees[num].lc)a+=dfs1(trees[num].lc,f);
    
22.         if(trees[num].rc)a+=dfs1(trees[num].rc,f);
    
23.         return a;
    
24. }
    
25. void dfs2(int i){
    
26.        
    
27.         if(trees[i].fa)trees[i].c=trees[trees[i].fa].c+1;
    
28.         //cout<<i<<" "<<trees[i].c<<" "<<trees[i].lc<<" "<<trees[i].rc<<endl;
    
29.         if(trees[i].lc)dfs2(trees[i].lc);
    
30.         if(trees[i].rc)dfs2(trees[i].rc);
    
31. }
    
32. int main(){
    
33.         int n;cin >> n;
    
34.         ios::sync_with_stdio(false);
    
35.         cin.tie(0);cout.tie(0);
    
36.         for(int i=1;i<n;i++){
    
37.                 int u,v;
    
38.                 cin>>u>>v;
    
39.                 if(trees[u].lc){
    
40.                         trees[u].rc=v;
    
41.                         trees[v].fa=u;
    
42.                 }
    
43.                 else{
    
44.                         trees[u].lc=v;
    
45.                         trees[v].fa=u;
    
46.                 }
    
47.                
    
48.         }
    
49.         int treeup=1;
    
50.         while(trees[treeup].fa){
    
51.                 treeup=trees[treeup].fa;
    
52.         }
    
53.         trees[treeup].c=1;
    
54.         //trees[i].c=trees[trees[i].fa].c+1;
    
55.         dfs2(treeup);
    
56.         dfs(1);
    
57.         for(int i=1;i<=n;i++){       
    
58.                 sum[trees[i].c]++;
    
59.                 resb=max(resb,sum[trees[i].c]);
    
60.         }
    
61.         int x,y;
    
62.         cin>>x>>y;
    
63.         int resc=1000000000;
    
64.         for(int i=1;i<=n;i++){
    
65.                
    
66.                 if(dfs1(i,x)&&dfs1(i,y)){
    
67.                         resc=min(resc,(trees[x].c-trees[i].c)*2+(trees[y].c-trees[i].c));
    
68.                 }
    
69.         }
    
70.         cout<<resa<<'\n'<<resb<<'\n'<<resc;
    
71.         return 0;
    
72. }
    
73. 
    
74. 
    

复制代码

不打表方法！

第1测试点，不保证父节点编号大于子节点

所以要用dfs方式赋值

有图为证：



思路：

爆搜LCA

PS：LCA，        &#8203;最近公共祖先。

加上

1. ios::sync_with_stdio(false);
   
2. cin.tie(0);cout.tie(0);

复制代码

效率更快

zhangjinxuan

xiaosi4081 发表于 2022-11-6 16:38
不打表方法！

第1测试点，不保证父节点编号大于子节点

可以，就是效率有点逊^_^

xiaosi4081

zhangjinxuan 发表于 2022-11-6 16:41
可以，就是效率有点逊^_^

问题不大吧

zhangjinxuan

xiaosi4081 发表于 2022-11-6 16:44
问题不大吧

把cout,cin改为printf,scanf就好了^_^

lxping

来顶

zhangjinxuan

有人吗？没人我撤了哦

zhangjinxuan

xiaosi4081 发表于 2022-11-6 16:38
不打表方法！

第1测试点，不保证父节点编号大于子节点

有人以35毫秒的成绩打败了你的37毫秒的代码~

zhangjinxuan

zhangjinxuan 发表于 2022-11-7 19:02
有人吗？没人我撤了哦

应该没人了，我撤了

Azhbdhlxt

顶一个