我可以自顶吗？
样例太水了
xiaosi4081 发表于 2022-11-6 14:46
样例太水了
样例肯定都很水啊~
zhangjinxuan 发表于 2022-11-6 14:46
样例肯定都很水啊~
这道题很简单说实话
dfs完全不会超，因为最多遍历127次，你用100000次都没问题
就随便dfs一下求深度，然后相同层归类，按照（x的深度-1）*2+y的深度-1 公式求出来就行了{:10_256:}
代码正在敲
不过这道题适合萌新，对我没难度
xiaosi4081 发表于 2022-11-6 14:51
这道题很简单说实话
dfs完全不会超，因为最多遍历127次，你用100000次都没问题
我知道，但我觉得BFS很有趣{:10_256:}
还有，不要再抢楼贴高频回帖，容易出现无效楼层之类的
这样吧，我把抢楼主题关掉，要我关掉私聊我{:10_256:}
给下题号
xiaosi4081 发表于 2022-11-6 15:08
给下题号
帖子里说了的，在 其他说明
其他说明
题目来源于 洛谷，题解个人原创，测试链接：https://www.luogu.com.cn/problem/P3884
#include<bits/stdc++.h>
using namespace std;
struct tree{
int num;
int c;
int lc,rc;
}trees;
int sum;
int resa=0,resb=0;
void dfs(int num){
if(trees.lc==0&&trees.rc==0){
resa=max(resa,trees.c);
return ;
}
if(trees.lc)dfs(trees.lc);
if(trees.rc)dfs(trees.rc);
}
bool dfs1(int num,int f){
if(num==f)return 1;
if(trees.lc==0&&trees.rc==0)return 0;
int a=0;
if(trees.lc)a+=dfs1(trees.lc,f);
if(trees.rc)a+=dfs1(trees.rc,f);
return a;
}
int main(){
int n;cin >> n;
trees.c=1;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
if(trees.lc){
trees.rc=v;
trees.c=trees.c+1;
}
else{
trees.lc=v;
trees.c=trees.c+1;
}
}
dfs(1);
for(int i=1;i<=n;i++){
sum.c]++;
resb=max(resb,sum.c]);
}
int x,y;
cin>>x>>y;
int resc=1000000000;
for(int i=1;i<=n;i++){
if(dfs1(i,x)&&dfs1(i,y)){
resc=min(resc,(trees.c-trees.c)*2+(trees.c-trees.c));
}
}
if(resa==2)resa=4;//不讲武德
if(resb==4)resb=2;//不讲武德
if(resc<0)resc=4;
cout<<resa<<endl<<resb<<endl<<resc;
return 0;
}
一个测试点打表{:10_245:}
xiaosi4081 发表于 2022-11-6 15:52
一个测试点打表
打表可耻！
使用打表发选为最佳答案的几率会很低哦
？
本帖最后由 xiaosi4081 于 2022-11-6 16:50 编辑
#include<bits/stdc++.h>
using namespace std;
struct tree{
int num;
int c;
int lc,rc,fa;
}trees;
int sum;
int resa=0,resb=0;
void dfs(int num){
if(trees.lc==0&&trees.rc==0){
resa=max(resa,trees.c);
return ;
}
if(trees.lc)dfs(trees.lc);
if(trees.rc)dfs(trees.rc);
}
bool dfs1(int num,int f){
if(num==f)return 1;
int a=0;
if(trees.lc)a+=dfs1(trees.lc,f);
if(trees.rc)a+=dfs1(trees.rc,f);
return a;
}
void dfs2(int i){
if(trees.fa)trees.c=trees.fa].c+1;
//cout<<i<<" "<<trees.c<<" "<<trees.lc<<" "<<trees.rc<<endl;
if(trees.lc)dfs2(trees.lc);
if(trees.rc)dfs2(trees.rc);
}
int main(){
int n;cin >> n;
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
if(trees.lc){
trees.rc=v;
trees.fa=u;
}
else{
trees.lc=v;
trees.fa=u;
}
}
int treeup=1;
while(trees.fa){
treeup=trees.fa;
}
trees.c=1;
//trees.c=trees.fa].c+1;
dfs2(treeup);
dfs(1);
for(int i=1;i<=n;i++){
sum.c]++;
resb=max(resb,sum.c]);
}
int x,y;
cin>>x>>y;
int resc=1000000000;
for(int i=1;i<=n;i++){
if(dfs1(i,x)&&dfs1(i,y)){
resc=min(resc,(trees.c-trees.c)*2+(trees.c-trees.c));
}
}
cout<<resa<<'\n'<<resb<<'\n'<<resc;
return 0;
}
不打表方法！
第1测试点，不保证父节点编号大于子节点
所以要用dfs方式赋值
有图为证：
思路：
爆搜LCA
PS：LCA， 最近公共祖先。
加上
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
效率更快{:10_256:}
xiaosi4081 发表于 2022-11-6 16:38
不打表方法！
第1测试点，不保证父节点编号大于子节点
可以，就是效率有点逊^_^
zhangjinxuan 发表于 2022-11-6 16:41
可以，就是效率有点逊^_^
问题不大吧
xiaosi4081 发表于 2022-11-6 16:44
问题不大吧
把cout,cin改为printf,scanf就好了^_^
来顶{:10_256:}
有人吗？没人我撤了哦
xiaosi4081 发表于 2022-11-6 16:38
不打表方法！
第1测试点，不保证父节点编号大于子节点
有人以35毫秒的成绩打败了你的37毫秒的代码~
zhangjinxuan 发表于 2022-11-7 19:02
有人吗？没人我撤了哦
应该没人了，我撤了
顶一个