二叉树
【深基16.例1】淘汰赛
题目描述
有 \(2^n\)（\(n\le7\)）个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1
号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4
号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？
输入格式
第一行一个整数 \(n\)，表示一共 \(2^n\) 个国家参赛。
第二行 \(2^n\) 个整数，第 \(i\) 个整数表示编号为 \(i\) 的国家的能力值（\(1\leq i \leq 2^n\)）。
数据保证不存在平局。
输出格式
仅一个整数，表示亚军国家的编号。
样例 #1
样例输入 #1
样例输出 #1
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
| #include<iostream>
using namespace std;
struct {
int val, num;
}a[10000000];
int main()
{
int n;
cin >> n;
int t = 1;
for (int i = (1<<n); i < (1<<(n+1)); i++)
{
cin >> a[i].val;
a[i].num = t;
t++;
}
for (int i = (1<<n)-1; i >1 ; i--)
{
if (a[2*i].val<a[2*i+1].val)
{
a[i] = a[2 * i + 1];
}
else
{
a[i] = a[2 * i];
}
}
if (a[2].val<a[3].val)
{
cout << a[2].num;
}
else
{
cout << a[3].num;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int tmp,n,tmp2,p,ans;
struct cou{
int en;
int ta;
}a[200];
bool cmp(cou x,cou y)
{
return x.en>y.en;
}
int main()
{
cin>>tmp;
n=pow(2,tmp);
for(int i=1;i<=n;i++){
cin>>a[i].en;
a[i].ta=i;
}
sort(a+1,a+n/2+1,cmp);
sort(a+n/2+1,a+n+1,cmp);
if(a[1].en>a[n/2+1].en){
cout<<a[n/2+1].ta;
}
else{
cout<<a[1].ta;
}
return 0;
}
|
【深基16.例3】二叉树深度
题目描述
有一个 \(n(n \le 10^6)\)
个结点的二叉树。给出每个结点的两个子结点编号（均不超过 \(n\)），建立一棵二叉树（根节点的编号为 \(1\)），如果是叶子结点，则输入
0 0。
建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。
输入格式
第一行一个整数 \(n\)，表示结点数。
之后 \(n\) 行，第 \(i\) 行两个整数 \(l\)、\(r\)，分别表示结点 \(i\) 的左右子结点编号。若 \(l=0\) 则表示无左子结点，\(r=0\) 同理。
输出格式
一个整数，表示最大结点深度。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
8
| 7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
|
样例输出 #1
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
| #include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int l, r;
}tree[100000000];
int ans = -1;
void dfs(int pos, int deep)
{
if (tree[pos].l==0&&tree[pos].r==0)
{
ans = max(ans, deep);
return;
}
if (tree[pos].l)
{
dfs(tree[pos].l, deep+1);
}
if (tree[pos].r)
{
dfs(tree[pos].r, deep+1);
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <=n ; i++)
{
cin >> tree[i].l >> tree[i].r;
}
dfs(1, 1);
cout << ans;
}
|
[USACO3.4] 美国血统
American Heritage
题目描述
农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛
们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而
不是用图形的方法。
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的
后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。（你可能已经知道你可以在知道树的两
种遍历以后可以经常地重建这棵树。）显然，这里的树不会有多于 \(26\) 个的顶点。
这是在样例输入和样例输出中的树的图形表达方式：
1
2
3
4
5
6
7
8
9
| C
/ \
/ \
B G
/ \ /
A D H
/ \
E F
|
附注：
- 树的中序遍历是按照左子树，根，右子树的顺序访问节点；
- 树的前序遍历是按照根，左子树，右子树的顺序访问节点；
- 树的后序遍历是按照左子树，右子树，根的顺序访问节点。
输入格式
第一行一个字符串，表示该树的中序遍历。
第二行一个字符串，表示该树的前序遍历。
输出格式
单独的一行表示该树的后序遍历。
样例 #1
样例输入 #1
样例输出 #1
提示
题目翻译来自NOCOW。
USACO Training Section 3.4
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
| 前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
#include<iostream>
using namespace std;
void dfs(string s1, string s2)
{
char root = s2[0];
int l = s1.find(root);
int r = s1.size() - 1 - l;
if (l)
{
string s1_l = s1.substr(0, l);
string s2_l = s2.substr(1, l);
dfs(s1_l, s2_l);
}
if (r)
{
string s1_r = s1.substr(l + 1, r);
string s2_r = s2.substr(l + 1, r);
dfs(s1_r, s2_r);
}
cout << root;
}
int main()
{
string s1, s2;;
cin >> s1 >> s2;
dfs(s1, s2);
}
|
偷盗题解两个图以加深理解（）
img
找到C
并且左右子树就可以知道了
然后截取就行
img
【深基16.例7】普通二叉树（简化版）
题目描述
您需要写一种数据结构，来维护一些数（都是绝对值 \(10^9\)
以内的数）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数
\(q\) 不超过 \(10^4\)：
- 定义数 \(x\) 的排名为集合中小于
\(x\) 的数的个数 \(+1\)。查询数 \(x\) 的排名。注意 \(x\) 不一定在集合里。
- 查询排名为 \(x(x\ge 1)\)
的数。保证集合里至少有 \(x\)
个数。
- 求 \(x\) 的前驱（前驱定义为小于
\(x\)，且最大的数）。若不存在则输出
\(-2147483647\)。
- 求 \(x\) 的后继（后继定义为大于
\(x\)，且最小的数）。若不存在则输出
\(2147483647\)。
- 插入一个数 \(x\)，本题的数据保证插入前 \(x\) 不在集合中。
保证执行 \(1,3,4\)
操作时，集合中有至少一个元素。
输入格式
第一行是一个整数 \(q\)，表示操作次数。
接下来 \(q\) 行，每行两个整数 \(op,x\)，分别表示操作序号以及操作的参数
\(x\)。
输出格式
输出有若干行。对于操作 \(1,2,3,4\)，输出一个整数，表示该操作的结果。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
8
| 7
5 1
5 3
5 5
1 3
2 2
3 3
4 3
|
样例输出 #1
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
|
#include<iostream>
#include<algorithm>
using namespace std;
int a[10000000];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, opt,x, cnt = 1;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> opt >> x;
if (opt==1)
{
cout << lower_bound(a + 1, a + cnt, x) - a << "\n";
}
if (opt==2)
{
cout << a[x] << "\n";
}
if (opt==3)
{
int tmp = lower_bound(a + 1, a + cnt, x) - a;
if (tmp==1)
{
cout << -2147483647 << "\n";
}
else
{
cout << a[tmp - 1] << "\n";
}
}
if (opt==4)
{
int tmp = upper_bound(a + 1, a + cnt, x) - a;
if (tmp == cnt)
{
cout << 2147483647 << "\n";
}
else
{
cout << a[tmp ] << "\n";
}
}
if (opt==5)
{
a[cnt] = x;
cnt++;
sort(a + 1, a + cnt);
}
}
}
|
正解--二叉搜索树
我爱题解，因为学到了新东西
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| #include<bits/stdc++.h>
#define re register
using namespace std;
const int INF=0x7fffffff;
int cont;
struct node{
int val,siz,cnt,ls,rs;
}tree[1000010];
int n,opt,xx;
inline void add(int x,int v)
{
tree[x].siz++;
if(tree[x].val==v){
tree[x].cnt++;
return ;
}
if(tree[x].val>v){
if(tree[x].ls!=0)
add(tree[x].ls,v);
else{
cont++;
tree[cont].val=v;
tree[cont].siz=tree[cont].cnt=1;
tree[x].ls=cont;
}
}
else{
if(tree[x].rs!=0)
add(tree[x].rs,v);
else{
cont++;
tree[cont].val=v;
tree[cont].siz=tree[cont].cnt=1;
tree[x].rs=cont;
}
}
}
int queryfr(int x, int val, int ans) {
if (tree[x].val>=val)
{
if (tree[x].ls==0)
return ans;
else
return queryfr(tree[x].ls,val,ans);
}
else
{
if (tree[x].rs==0)
return tree[x].val;
return queryfr(tree[x].rs,val,tree[x].val);
}
}
int queryne(int x, int val, int ans) {
if (tree[x].val<=val)
{
if (tree[x].rs==0)
return ans;
else
return queryne(tree[x].rs,val,ans);
}
else
{
if (tree[x].ls==0)
return tree[x].val;
return queryne(tree[x].ls,val,tree[x].val);
}
}
int queryrk(int x,int rk)
{
if(x==0) return INF;
if(tree[tree[x].ls].siz>=rk)
return queryrk(tree[x].ls,rk);
if(tree[tree[x].ls].siz+tree[x].cnt>=rk)
return tree[x].val;
return queryrk(tree[x].rs,rk-tree[tree[x].ls].siz-tree[x].cnt);
}
int queryval(int x,int val)
{
if(x==0) return 0;
if(val==tree[x].val) return tree[tree[x].ls].siz;
if(val<tree[x].val) return queryval(tree[x].ls,val);
return queryval(tree[x].rs,val)+tree[tree[x].ls].siz+tree[x].cnt;
}
int main()
{
cin>>n;
while(n--){
cin>>opt;cin>>xx;
if(opt==1) cout<<queryval(1,xx)+1<<'\n';
else if(opt==2) cout<<queryrk(1,xx)<<'\n';
else if(opt==3) cout<<queryfr(1,xx,-INF)<<'\n';
else if(opt==4) cout<<queryne(1,xx,INF)<<'\n';
else{
if(cont==0){
cont++;
tree[cont].cnt=tree[cont].siz=1;
tree[cont].val=xx;
}
else add(1,xx);
}
}
}
|
题解中还有另外一种解决思路
姑且借鉴（抄袭）
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
| multiset<int>q;
q.insert(x);
q.clear();
q.erase(x);
q.erase(it);
q.empty();
q.size()
q.begin();
q.end();
q.count(x);
q.find(x);
q.lower_bound(x);
q.upper_bound(x);
|
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
multiset<int>q;
int n,t,x,order;
int main()
{
q.insert(-0x7fffffff);
q.insert(0x7fffffff);
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&t,&x);
if(t==1)
{
auto it=q.lower_bound(x);
order=0;
for(auto i=q.begin();i!=it;i++,order++);
printf("%d\n",order);
}
else if(t==2)
{
order=-1;
for(int i:q)
if(++order==x)
printf("%d\n",i);
}
else if(t==3)
{
auto it=q.lower_bound(x);
printf("%d\n",*--it);
}
else if(t==4)
{
printf("%d\n",*q.upper_bound(x));
}
else
{
q.insert(x);
}
}
return 0;
}
|
医院设置
题目描述
设有一棵二叉树，如图：
其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为
\(1\)。如上图中，若医院建在 \(1\) 处，则距离和 \(=4+12+2\times20+2\times40=136\)；若医院建在
\(3\) 处，则距离和 \(=4\times2+13+20+40=81\)。
输入格式
第一行一个整数 \(n\)，表示树的结点数。
接下来的 \(n\)
行每行描述了一个结点的状况，包含三个整数 \(w,
u, v\)，其中 \(w\)
为居民人口数，\(u\) 为左链接（为 \(0\) 表示无链接），\(v\) 为右链接（为 \(0\) 表示无链接）。
输出格式
一个整数，表示最小距离和。
样例 #1
样例输入 #1
1
2
3
4
5
6
| 5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
|
样例输出 #1
提示
数据规模与约定
对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 100\)，\(0 \leq u, v \leq n\)，\(1 \leq w \leq 10^5\)。
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
| #include<bits/stdc++.h>
using namespace std;
struct node
{
int left;
int right;
int father;
int value;
}t[105];
int n, sum, ans=INT_MAX, vis[105];
void dfs(int step, int pos)
{
sum += step * t[pos].value;
int fa = t[pos].father, l = t[pos].left, r = t[pos].right;
if (fa && !vis[fa])
{
vis[fa] = 1;
dfs(step + 1, fa);
}
if (l && !vis[l])
{
vis[l] = 1;
dfs(step + 1, l );
}
if (r && !vis[r])
{
vis[r] = 1;
dfs(step + 1, r);
}
}
int main()
{
cin >> n;
for (int i = 1; i <=n ; i++)
{
cin >> t[i].value >> t[i].left >> t[i].right;
t[t[i].left].father = i;
t[t[i].right].father = i;
}
for (int i = 1; i <=n ; i++)
{
sum = 0;
memset(vis, 0, sizeof(vis));
vis[i] = 1;
dfs(0,i);
ans = min(ans, sum);
}
cout << ans;
}
|
遍历问题
题目描述
我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
输入格式
共两行，第一行表示该二叉树的前序遍历结果 \(s_1\)，第二行表示该二叉树的后序遍历结果
\(s_2\)。
输出格式
输出可能的中序遍历序列的总数，结果不超过 \(2^{63}-1\)。
样例 #1
样例输入 #1
样例输出 #1
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
|
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s1, s2;
cin >> s1 >> s2;
long long ans = 1;
for (int i = 0; i <=s1.length()-2 ; i++)
{
for (int j = 0; j <=s1.length()-1; j++)
{
if (s1[i]==s2[j])
{
if (s1[i+1]==s2[j-1])
{
ans *= 2;
break;
}
}
}
}
cout << ans;
}
|
新二叉树
题目描述
输入一串二叉树，输出其前序遍历。
输入格式
第一行为二叉树的节点数 \(n\)。(\(1 \leq n \leq 26\))
后面 \(n\)
行，每一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。
空节点用 * 表示
输出格式
二叉树的前序遍历。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
| 6
abc
bdi
cj*
d**
i**
j**
|
样例输出 #1
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
|
#include<iostream>
#include<string>
using namespace std;
struct node {
char l, r;
}tree[200];
void dfs(char pos)
{
cout << pos;
if (tree[pos].l!='*')
{
dfs(tree[pos].l);
}
if (tree[pos].r!='*')
{
dfs(tree[pos].r);
}
}
int main()
{
int n;
cin >> n;
char a, l, r,bg ;
cin >> bg >> l >> r;
tree[bg].l = l;
tree[bg].r = r;
for (int i = 1; i < n; i++)
{
cin >> a >> l >> r;
tree[a].l = l;
tree[a].r = r;
}
dfs(bg);
return 0;
}
|
[NOIP2001 普及组] 求先序排列
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数
$ $）。
输入格式
共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式
共一行一个字符串，表示一棵二叉树的先序。
样例 #1
样例输入 #1
样例输出 #1
提示
【题目来源】
NOIP 2001 普及组第三题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void be(string in,string after){
if (in.size()>0){
char ch=after[after.size()-1];
cout<<ch;
int k=in.find(ch);
be(in.substr(0,k),after.substr(0,k));
be(in.substr(k+1),after.substr(k,in.size()-k-1));
}
}
int main(){
string in,af;
cin>>in;cin>>af;
be(in,af);
}
|
[JLOI2009] 二叉树问题
题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：
- 深度：\(4\)
- 宽度：\(4\)
- 结点 8 和 6 之间的距离：\(8\)
- 结点 7 和 6 之间的距离：\(3\)
其中宽度表示二叉树上同一层最多的结点个数，节点 \(u, v\) 之间的距离表示从 \(u\) 到 \(v\)
的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。
img
给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点
\(x, y\) 之间的距离。
输入格式
第一行是一个整数，表示树的结点个数 \(n\)。
接下来 \(n - 1\) 行，每行两个整数 \(u, v\)，表示树上存在一条连接 \(u, v\) 的边。
最后一行有两个整数 \(x, y\)，表示求
\(x, y\) 之间的距离。
输出格式
输出三行，每行一个整数，依次表示二叉树的深度、宽度和 \(x, y\) 之间的距离。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
8
9
10
11
| 10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6
|
样例输出 #1
提示
对于全部的测试点，保证 \(1 \leq u, v, x, y
\leq n \leq 100\)，且给出的是一棵树。
LCA最近公共祖先
向上标记法
向上标记法是求LCA最直接的方法，直接根据定义来求，单次查询的时间复杂度最坏为O(n)
算法流程：
- 从x节点向上一直走到根节点，沿途标记经过的节点
- 从y节点向上一直走到根节点，当第一次遇到已标记的节点时，该节点就是LCA(x,y）
树上倍增法
用树上倍增法求LCA的时间复杂度为O((n+m)logn)
树上倍增法用到了二进制拆分的思想。在求LCA时，用f[i]
[j]存储i的第2的j次方辈祖先的节点编号，特别地，若该节点不存在，则将值定为0。根据这个定义，可以推出以下的递推式：
1
| f[i][j]=f[f[i][j-1]][j-1];
|
一个节点的f数组的值要通过它的祖先节点转移过来，因此我们在递推时要采用从根到叶子的遍历。普遍使用的方法有dfs和bfs，在这里我们用bfs来实现。
步骤：
- 建立一个空队列，并将根节点入队，同时存储根节点的深度
- 取出队头，遍历其所有出边。由于存储的时候是按照无向图存储，因此要进行深度判定，对于连接到它父亲节点的边，直接continue即可。记当前路径的另一端节点为y，处理出y的d、f两个数组的值，然后将y入队。
- 重复第2步，直到队列为空
以上部分是树上倍增法的预处理，
【模板】最近公共祖先（LCA）
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 \(N,M,S\)，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 \(N-1\) 行每行包含两个正整数
\(x, y\)，表示 \(x\) 结点和 \(y\)
结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 \(M\) 行每行包含两个正整数
\(a, b\)，表示询问 \(a\) 结点和 \(b\) 结点的最近公共祖先。
输出格式
输出包含 \(M\)
行，每行包含一个正整数，依次为每一个询问的结果。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
8
9
10
| 5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
|
样例输出 #1
提示
对于 \(30\%\) 的数据，\(N\leq 10\)，\(M\leq 10\)。
对于 \(70\%\) 的数据，\(N\leq 10000\)，\(M\leq 10000\)。
对于 \(100\%\) 的数据，\(1 \leq N,M\leq 500000\)，\(1 \leq x, y,a ,b \leq
N\)，不保证 \(a \neq
b\)。
样例说明：
该树结构如下：
第一次询问：\(2, 4\)
的最近公共祖先，故为 \(4\)。
第二次询问：\(3, 2\)
的最近公共祖先，故为 \(4\)。
第三次询问：\(3, 5\)
的最近公共祖先，故为 \(1\)。
第四次询问：\(1, 2\)
的最近公共祖先，故为 \(4\)。
第五次询问：\(4, 5\)
的最近公共祖先，故为 \(4\)。
故输出依次为 \(4, 4, 1, 4, 4\)。
2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。
> > 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
| #include<bits/stdc++.h>
using namespace std;
const int N=6e5;
int n,m,s,t,tot=0,f[N][20],d[N],ver[2*N],Next[2*N],head[N];
queue<int> q;
void add(int x,int y)
{
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void bfs()
{
q.push(s);
d[s]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
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])
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()
{
cin>>n>>m>>s;
t=log2(n)+1;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
add(x,y),add(y,x);
}
bfs();
while(m--)
{
int a,b;
cin>>a>>b;
cout<<lca(a,b)<<'\n';
}
return 0;
}
|
接下来回头看这个问题（为了一道题去学另一道题）
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
| #include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,u,v,t,tot,ans,lca;
int d[N],dep[10],f[N][10];
int head[N],Next[2*N],ver[2*N];
void add(int x,int y)
{
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void bfs()
{
queue<int> q;
d[1]=1,dep[1]++;
q.push(1);
while(q.size())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(d[y])
continue;
d[y]=d[x]+1;
dep[d[y]]++;
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])
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()
{
cin>>n;
t=log2(n)+1;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
add(x,y),add(y,x);
}
cin>>u>>v;
bfs();
lca=LCA(u,v);
for(int i=1;i<=n;i++)
ans=max(ans,d[i]);
cout<<ans<<'\n';
ans=0;
for(int i=1;i<=t;i++)
ans=max(ans,dep[i]);
cout<<ans<<'\n'<<(d[u]-d[lca])*2+d[v]-d[lca];
}
|
模板库可以更新了（）
绘制二叉树
题目描述
二叉树是一种基本的数据结构，它要么为空，要么由根结点，左子树和右子树组成，同时左子树和右子树也分别是二叉树。
当一颗二叉树高度为 \(m-1\) 时，共有
\(m\) 层。若一棵二叉树除第 \(m\)
层外，其他各层的结点数都达到最大，且叶子结点都在第 \(m\) 层时，则其为一棵满二叉树。
现在，需要你用程序来绘制一棵二叉树，它由一棵满二叉树去掉若干结点而成。对于一棵满二叉树，我们需要按照以下要求绘制：
结点用小写字母 o 表示，对于一个父亲结点，用
/ 连接左子树，用 \ 连接右子树。
定义 \([i,j]\) 为位于第 \(i\) 行第 \(j\) 列的某个字符。若 \([i,j]\) 为 / ，那么 \([i-1,j+1]\) 与 \([i+1,j-1]\) 要么为 o ，要么为
/。若 \([i,j]\) 为
\ ，那么 \([i-1,j-1]\) 与
\([i+1,j+1]\) 要么为
o，要么为 \ 。同样，若 \([i,j]\) 为第 \(1\sim m-1\) 层的某个结点 o
，那么 \([i+1,j-1]\) 为
/，\([i+1,j+1]\) 为
\。
对于第 \(m\)
层结点也就是叶子结点点，若两个属于同一个父亲，那么它们之间由 \(3\)
个空格隔开；若两个结点相邻但不属于同一个父亲，那么它们之间由 \(1\) 个空格隔开。第 \(m\) 层左数第 \(1\) 个结点之前没有空格。
最后需要在一棵绘制好的满二叉树上删除 \(n\)
个结点（包括这个结点的左右子树，以及与父亲的连接），原有的字符用空格替换（空格为
ASCII 32，若输出 ASCII 0
会被算作错误答案）。
输入格式
第 \(1\) 行包含 \(2\) 个正整数 \(m\) 和 \(n\)，为需要绘制的二叉树层数和需要删除的结点数。
接下来 \(n\)
行，每行两个正整数，表示删除第 \(i\)
层的第 \(j\) 个结点。
输出格式
按照题目要求绘制的二叉树。
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
1
2
3
4
5
6
7
8
9
10
11
12
| o
/ \
/ \
/ \
/ \
/ \
o o
/ \ / \
/ \ / \
o o o o
/ \ / \ / \ / \
o o o o o o o o
|
样例 #3
样例输入 #3
样例输出 #3
1
2
3
4
5
6
7
8
9
10
11
12
| o
/ \
/ \
/ \
/ \
/ \
o o
/ /
/ /
o o
\ / \
o o o
|
提示
\(30\%\) 的数据满足：\(n=0\)；
\(50\%\) 的数据满足：\(2\le m\le 5\)；
\(100\%\) 的数据满足：\(2\le m\le10,0\le n\le 10,1<i\le M,j\le
2^{i-1}\)。
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 <bits/stdc++.h>
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int N = 3100;
int len[20],m,n,pos[20],h[20];
char a[N][N];
void prepare(){
int sum = 1;
len[1] = 1;pos[1] = 1;
rep(i,2,m) {
len[i] = sum + i-1;
sum += len[i];
pos[i] = len[i] + 1;
}
h[m] = 1;
for(int i = m-1; i ;i --)
{
h[i] = h[i+1]+len[i]+1;
}
memset(a,' ',sizeof(a));
}
void draw(int x,int y,int depth){
a[x][y] = 'o';
if(depth == 1) return;
int lx = x+1,ly = y-1,rx = x+1,ry = y+1;
rep(i,1,len[depth-1])
{
a[lx][ly] = '/';
a[rx][ry] = '\\';
lx = lx+1,ly = ly-1,rx = rx+1,ry = ry+1;
}
draw(lx,ly,depth-1);
draw(rx,ry,depth-1);
}
void destroy(int x,int y){
a[x][y] = ' ';
if(a[x-1][y-1] == '\\') destroy(x-1,y-1);
if(a[x-1][y+1] == '/') destroy(x-1,y+1);
if(a[x+1][y-1] == '/' || a[x+1][y-1] == 'o') destroy(x+1,y-1);
if(a[x+1][y+1] == '\\'|| a[x+1][y+1] == 'o') destroy(x+1,y+1);
}
void print(){
int height = h[1];
int width = 6 * (1<<(m-1));
rep(i,1,height){
rep(j,1,width)
cout<<a[i][j];
cout<<'\n';
}
}
int main(){
cin>>m>>n;
prepare();
draw(1,pos[m],m);
while(n--)
{
int i,j;
cin>>i>>j;
if(i > 10) continue;
int x = h[m+1-i],y;
if(i == m)
{
if(j & 1) y = pos[1] + j/2*6;
else y = pos[1] + j/2*6 - 2;
}
else y = pos[m+1-i] + (j-1)* (2 * len[m+1-i] + 2);
destroy(x,y);
}
print();
}
|
世间温柔，不过是芳春柳摇染花香，槐序蝉鸣入深巷，白茂叶落醉故乡。
人生何处不相逢，各位再见。
