「题解」Luogu 3884「[JLOI2009]二叉树问题」

分析

读入的时候就可统计深度与宽度(因为这题数据比较弱智),然后再跑一个LCA就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
const int MAXN = 100 + 6;
int sum[MAXN],f[MAXN][20],d[MAXN],t;
class BTNode{
public:
int left,right,p,id,depth;
BTNode(){
left = right = p = 0;
}
BTNode(int id){
this -> id = id;
this -> depth = 0;
left = right = p = 0;
}
};BTNode T[MAXN];
struct Edge{
int v,d;
Edge(){}
Edge(int v,int d){
this -> v = v;
this -> d = d;
}
};
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge(int u,int v){G[u].push_back(Edge(v,666));}
void bfs(int s){
int x,y;
Q.push(s);
d[s] = 1;
while(Q.size()){
x = Q.front();Q.pop();
for(int i = 0;i < G[x].size();i++){
y = G[x][i].v;
if(d[y]) continue;
d[y] = d[x] + 1;
f[y][0] = x;
for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
Q.push(y);
}
}
}
int lca(int x,int y){
if(d[x] > d[y]) std::swap(x,y);
for(int i = t;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];
if(x == y) return x;
for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
return f[x][0];
}

int main(){
int n,u,v,max = 0,r;scanf("%d",&n);
T[1].depth = 1;T[1].p = 0;
T[1].depth = 1;
t = (int)log(n) / log(2) + 1;
for(int i = 1;i < n;i++){
scanf("%d %d",&u,&v);
addEdge(u,v);addEdge(v,u);
if(T[u].left == 0) T[u].left = v;
else T[u].right = v;
T[v].p = u;
T[v].depth = T[u].depth + 1;
max = std::max(T[v].depth,max);
}
bfs(1);
for(int i = 1;i <= n;i++) sum[T[i].depth]++;
std::sort(sum + 1,sum + 1 + n);
scanf("%d %d",&u,&v);
r = lca(u,v);
printf("%d\n%d\n%d",max,sum[n],(T[u].depth - T[r].depth) * 2 + T[v].depth - T[r].depth);

return 0;
}
分享到