社区讨论
1,9,10WA,求助
P3884[JLOI2009] 二叉树问题参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo1zak5s
- 此快照首次捕获于
- 2023/10/23 05:26 2 年前
- 此快照最后确认于
- 2023/11/03 05:50 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
struct node{
int father;int left;int right;int deep;
};
node f[110];
int n;
int a,b,c,d,pd = 0;
int res = 0,idx = 1;
int ans1,ans2,ans3;
int tong[110],vis[110] = {0};
void dfs(int root,int dp) {
if(root == 0) return;
f[root].deep = dp;
tong[dp]++;
dfs(f[root].left,dp + 1);
dfs(f[root].right,dp + 1);
}
void getDis(int st,int ed,int dis) {
if(st == 0 || vis[st]) return;
if(st == ed) {pd = 1; ans3 = dis; return;}
vis[st] = 1;
if(!pd) {
getDis(f[st].left,ed,dis + 1);
getDis(f[st].right,ed,dis + 1);
getDis(f[st].father,ed,dis + 1);
}
}
int main(){
cin >> n;
for(int i = 1;i < n;i++) {
cin >> a >> b;
if(f[a].left == 0) f[a].left = b;
else f[a].right = b;
f[b].father = a;
}
dfs(1,1);
for(int i = 1;i <= n;i++) {
ans1 = max(ans1,f[i].deep);
ans2 = max(ans2,tong[i]);
}
cin >> c >> d;
getDis(c,1,0);
res += ans3 * 2;
pd = 0;
getDis(1,d,0);
res += ans3;
cout << ans1 << '\n' << ans2 << '\n' << res << endl;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...