社区讨论
82分求助!
P3884[JLOI2009] 二叉树问题参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m1iu6l4e
- 此快照首次捕获于
- 2024/09/26 13:11 去年
- 此快照最后确认于
- 2024/09/26 18:13 去年
CPP
#include <bits/stdc++.h>
#define clear memset(f, 0, sizeof(f));
using namespace std;
const int N = 105;
int n, x, y, sd, kd, cnt[N];
bool f[N], f_up, f_down;
struct node{
int father = -1, lson = -1, rson = -1;
} a[N];
void dfs(int x, int sum)
{
if (a[x].lson != -1 && !f[a[x].lson])
{
// cout << sum << endl;
f[a[x].lson] = 1;
cnt[sum+1]++;
sd = max(sd, sum + 1);
dfs(a[x].lson, sum + 1);
}
if (a[x].rson != -1 && !f[a[x].rson])
{
// cout << sum << endl;
f[a[x].rson] = 1;
cnt[sum+1]++;
sd = max(sd, sum + 1);
dfs(a[x].rson, sum + 1);
}
}
struct node2{
int x, v;
};
int bfs(int qd, int zd)
{
queue<node2> q;
clear
f[qd] = 1;
q.push({qd, 0});
while (q.size())
{
node2 k = q.front();
q.pop();
if (k.x == zd)
{
return k.v;
}
if (a[k.x].father != -1 && !f[a[k.x].father])
{
f[a[k.x].father] = 1;
q.push({a[k.x].father, k.v + 1});
}
}
}
int bfs2(int qd, int zd)
{
queue<node2> q;
clear
f[qd] = 1;
q.push({qd, 0});
while (q.size())
{
node2 k = q.front();
q.pop();
if (k.x == zd)
{
return k.v;
}
if (a[k.x].lson != -1 && !f[a[k.x].lson])
{
f[a[k.x].lson] = 1;
q.push({a[k.x].lson, k.v + 1});
}
if (a[k.x].rson != -1 && !f[a[k.x].rson])
{
f[a[k.x].rson] = 1;
q.push({a[k.x].rson, k.v + 1});
}
}
}
void dfs_up(int v)
{
if (a[v].father != -1 && !f[a[v].father])
{
f[a[v].father] = 1;
if (a[v].father == y)
{
f_up = 1;
}
dfs_up(a[v].father);
}
}
void dfs_down(int v)
{
if (a[v].lson != -1 && !f[a[v].lson])
{
f[a[v].lson] = 1;
dfs_down(a[v].lson);
}
if (a[v].rson != -1 && !f[a[v].rson])
{
f[a[v].rson] = 1;
dfs_down(a[v].rson);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
if (a[u].lson == -1)
{
a[u].lson = v;
}
else
{
a[u].rson = v;
}
a[v].father = u;
}
cin >> x >> y;
f[1] = 1;
cnt[1] = 1;
dfs(1, 1);
kd = 0;
for (int i = 1; i <= sd; i++)
{
// cout << cnt[i] << ' ';
kd = max(kd, cnt[i]);
}
// cout << endl;
cout << sd << endl << kd << endl;
clear
dfs_up(x);
clear
dfs_down(y);
if (f_up)
{
cout << bfs(x, y) * 2;
}
else if (f_down)
{
cout << bfs2(x, y);
}
else
{
cout << bfs(x, 1) * 2 + bfs2(1, y);
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...