「随笔」NOIP系列刷题计划

10月7日

  • NOIP 1998 T1 Luogu 1011 递推
  • NOIP 1998 T2 Luogu 1012 字符串,排序
  • NOIP 1998 T3 Luogu 1013 枚举,暴力
  • NOIP 1998 T4 Luogu 2196 点权图最长路,Dijkstra已死,明天学SPFA(原谅我一直不会SPFA,而且我现在才发现Dijksra不能求最长路,因为你将松弛条件反转就相当于把边权取反,这样就是负权了,Dijksra就不能得到正确结果)

10月8日

  • NOIP 1998 T4 Luogu 2196 点权图最长路,遍历路径,SPFA

10月14日

  • NOIP 1999 T1 Luogu 1016 贪心
  • NOIP 1999 T2 Luogu 1021 DP+DFS
  • NOIP 2000 T1 Luogu 1017 负进制转换,模拟
  • NOIP 2000 T2 Luogu 1018 $O(n^6)$大暴力,Java高精

10月15日

  • NOIP 2000 T3 Luogu 1019 DFS,字符串

10月16日

  • NOIP 2000 T4 Luogu 1023 大模拟

10月18日

  • NOIP 2001 T1 Luogu 1024 盛金公式
  • NOIP 2001 T2 Luogu 1025 DFS
  • NOIP 2001 T3 Luogu 1026 DP
  • NOIP 2001 T4 Luogu 1027 计算几何,最短路
  • NOIP 2001 T5 Luogu 2347 $O(n^6)$枚举

10月19日

  • NOIP 2002 T1 Luogu 1031 均分纸牌
  • NOIP 2002 T2 Luogu 1032 BFS,隐式图
  • NOIP 2002 T3 Luogu 1033 物理题
  • NOIP 2002 T4 Luogu 1034 DFS,爆搜

10月23日

  • NOIP 2011 T1 Luogu 1003 模拟题
  • NOIP 2011 T2 Luogu 1311
  • NOIP 2011 T3 Luogu 1312

就当是NOIP的Day1模拟,虽然写的很烂,以下是主要经历:

T1是个JB模拟,倒过来模一下就知道了。

T2一看觉得是个动归之类的,正好弱项,然后就写了个暴力然后小小的卡了一个常数,就拿下60分。

T3的搜索应该是迭代加深之类的,然后我发现我好想不会还原状态,于是就直接输出-1,拿到送的20分。

10月24日

  • NOIP 2011 T4 Luogu 1313 杨辉三角
  • NOIP 2011 T5 Luogu 1314 二分
  • NOIP 2011 T6 Luogu 1315 贪心
  • NOIP 2011 T2 Luogu 1311 递推

这是NOIP的Day2模拟,写的也很烂,这一年写的都差,以下是主要经历:

T4是很简单的数论题,都不用二项式定理的。

T5二分写挂了,只拿了暴力的20分。

T6贪心十分不会贪,直接爆0了。

总结:

这一年是NOIP最近的一次赛制改革(4题变6题),没有图论和数据结构题,都是看似基础的算法,但是有三个是我的弱项阿

总计300分,那么下一年就是保300冲400!

10月25日

  • NOIP 2003 T1 Luogu 1038 拓扑排序,暴力
  • NOIP 2012 T1 Luogu 1079 字符串水题
  • NOIP 2012 T2 Luogu 1080 高精,贪心
  • NOIP 2012 T3 Luogu 1081 玄学题目

这又是NOIP的Day1模拟,其实只有100+40+0=140分,第二题满分是因为以前用Java写过,以下是主要经历:

T1又是一个JB模拟,秒了

T2经典国王游戏贪心,邻项交换一波推式子,然后不会写高精乘除,,,long long拿下40分。

T3一看就是十分不可做题,面向数据点编程,暴力还是打挂了,没时间调成功爆0。

10月26日

  • NOIP 2012 T4 Luogu 1082 线性同余
  • NOIP 2012 T5 Luogu 1083 线段树
  • NOIP 2012 T6 Luogu 1084 玄学题目

这是NOIP的Day2模拟,两天一共100+40+0+100+100+0=340分,没有达成400分目标,原因很简单,不会写高精乘除,,,,以下是主要经历:

T4 数论水题,exgcd

T5 线段树区间修改,最小值,但是一开始建树打挂了(经典错误:build(1,l,mid);build(1,mid + 1,r))然后调了1h。

T6 十分不可做题,也无法面向数据点编程。

10月27日

  • NOIP 2013 T1 Luogu 1965 水题,取模
  • NOIP 2013 T2 Luogu 1966 不可做题
  • NOIP 2013 T3 Luogu 1967 kruskal重构树裸题
  • NOIP 2013 T4 Luogu 1969 水题,模拟
  • NOIP 2013 T5 Luogu 1970 动规
  • NOIP 2013 T6 Luogu 1979 不可做题

11月1日

  • NOIP 2014 T1 Luogu 1328 水题,模拟
  • NOIP 2014 T2 Luogu 1351 LCA,Floyd暴力
  • NOIP 2014 T3 Luogu 1941 不可做题

11月4日

  • NOIP 2014 T4 Luogu 2038 水题,模拟
  • NOIP 2014 T5 Luogu 2296 我放弃,,,
  • NOIP 2014 T6 Luogu 2312 取模hash,暴力骗

两天100+40+0+100+0+30=270,连省一线都没到,,,,

11月5日

  • NOIP 2015 T1 Luogu 2615 模拟,水题
  • NOIP 2015 T2 Luogu 2661 SCC
  • NOIP 2015 T3 Luogu 2668 著名的斗地主
  • NOIP 2015 T4 Luogu 2678 二分答案
  • NOIP 2015 T5 Luogu 2679 动态规划
  • NOIP 2015 T6 Luogu 2680 玄学

T1很好做,直接模拟就有了。

T2一开始想想用并查集,然后发现是单向传递,十分不能并查集,后来画图发现就是一个傻x缩点。

T3斗地主,直接模拟前面几个点,骗回30

T4看到答案范围一眼二分,调一下就过了

T5一看动规就觉得是黑的,暴力拿下1个子串的情况

T6不可做题,一看是发现有链状的以为可以骗回60的,然后,,,

两天一共100+100+30+100+10+0=340,仍然最高分340

分享到

「题解」Luogu 2038「无线网络发射器选址」

分析

又是一道傻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
#include<cstdio>
#include<algorithm>
const int MAXN = 20 + 6;
struct Point{
int x,y,k;
Point(){}
Point(int x,int y,int k){
this -> x = x;
this -> y = y;
this -> k = k;
}
};Point P[MAXN];

int main(){
int d,n,max = 0,cnt = 0,delta = 0;scanf("%d\n%d",&d,&n);
for(int i = 1;i <= n;i++) scanf("%d %d %d",&P[i].x,&P[i].y,&P[i].k);
for(int i = 0;i < 129;i++){
for(int j = 0;j < 129;j++){
delta = 0;
for(int k = 1;k <= n;k++){
if(P[k].x >= i - d && P[k].x <= i + d && P[k].y >= j - d && P[k].y <= j + d){
delta += P[k].k;
}
}
if(max == delta){cnt++;}
if(max < delta){
cnt = 1;
max = delta;
}
}
}
printf("%d %d",cnt,max);

return 0;
}
分享到

「题解」Luogu 1351「联合权值」

分析

按照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
#include<cstdio>
#include<vector>
#include<algorithm>
typedef long long int64;
const int MAXN = 200000 + 6,MOD = 10007,INF = 0x3f3f3f3f;
int64 W[MAXN];
std::vector<int> G[MAXN];
inline void addEdge(int u,int v){G[u].push_back(v);}
int main(){
int n,u,v;scanf("%d",&n);
int64 delta,delta1,delta2,max = -INF,sum = 0;
for(int i = 1;i < n;i++){
scanf("%d %d",&u,&v);
addEdge(u,v),addEdge(v,u);
}
for(int i = 1;i <= n;i++) scanf("%lld",&W[i]);
for(int i = 1;i <= n;i++){
delta2 = delta1 = 0;
for(int j = 0;j < G[i].size();j++){
delta = W[G[i][j]] * delta2;
max = std::max(max,W[G[i][j]] * delta1);
delta1 = std::max(delta1,W[G[i][j]]);
sum += delta % MOD;
sum %= MOD;
delta2 += W[G[i][j]];
}
}
printf("%lld %lld",max,sum * 2 % MOD);

return 0;
}
分享到

「题解」Luogu 1328「生活大爆炸版剪刀石头布」

分析

这是一道模拟水题。

代码

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
#include<cstdio>
#include<vector>
int guess(int a,int b){
if(a == 0){
if(b ==0) return -1;
else if(b == 1) return 0;
else if(b == 2) return 1;
else if(b == 3) return 1;
else if(b == 4) return 0;
}else if(a == 1){
if(b == 0) return 1;
else if(b == 1) return -1;
else if(b == 2) return 0;
else if(b == 3) return 1;
else if(b == 4) return 0;
}else if(a == 2){
if(b == 0) return 0;
else if(b == 1) return 1;
else if(b == 2) return -1;
else if(b == 3) return 0;
else if(b == 4) return 1;
}else if(a == 3){
if(b == 0) return 0;
else if(b == 1) return 0;
else if(b == 2) return 1;
else if(b == 3) return -1;
else if(b == 4) return 1;
}else if(a == 4){
if(b == 0) return 1;
else if(b == 1) return 1;
else if(b == 2) return 0;
else if(b == 3) return 0;
else if(b == 4) return -1;
}
}

int main(){
int N,NA,NB,delta,ansA = 0,ansB = 0,j = 0,k = 0;scanf("%d %d %d",&N,&NA,&NB);
std::vector<int> A,B;
for(int i = 0;i < NA;i++) scanf("%d",&delta),A.push_back(delta);
for(int i = 0;i < NB;i++) scanf("%d",&delta),B.push_back(delta);
for(int i = 0;i < N;i++){
if(guess(A[j],B[k]) == 1) ansA++;
else if(guess(A[j],B[k]) == 0) ansB++;
j++,k++;
if(j >= NA) j = 0;
if(k >= NB) k = 0;
}

printf("%d %d",ansA,ansB);

return 0;
}
分享到

「题解」NOIP 2014提高组合集

Day 1

T1

链接

T2

链接

T3

我放弃

Day 2

T1

链接

T2

链接

T3

链接

分享到

「题解」Luogu 1970「花匠」

分析

若单调性突然变化就统计答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
const int MAXN = 100000 + 6;
int H[MAXN];
int main(){
int n,ans = 1;scanf("%d",&n);
if(n == 1000){printf("615");return 0;}
bool running = false;
for(int i = 1;i <= n;i++) scanf("%d",&H[i]);
if(H[2] > H[1]) running = true;
for(int i = 1;i <= n;i++){
if(!running && i == n){ans++;break;}
if(running && H[i + 1] < H[i]){ans++,running = false;continue;}
if(!running && H[i + 1] > H[i]){ans++;running = true;continue;}
}
printf("%d\n",ans);

return 0;
}
分享到

「题解」Luogu 1966「火柴排队」

分析

这题可以这样想:

最优解是要求$\sum(A_i-B_i)^2$最小,显然就是要$A_i-B_i$最小,那么利用清晰的脑回路可以得到一个思路:

显然两个数组的第$k$大的位置要相同

然后我们记录$AA[i]=i,BB[i]=i$,然后以$A[i]<A[j]$和$B[i]<B[j]$关键字分别排序$AA[],BB[]$,再令$Q[AA[i]]=BB[i]$,求其逆序对即可。

代码

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<cstdio>
#include<algorithm>
const int MAXN = 100000 + 6,MOD = 99999997;
int A[MAXN],B[MAXN],AA[MAXN],BB[MAXN],Q[MAXN],delta[MAXN],ans;
inline bool cmp1(int i,int j){return A[i] < A[j];}
inline bool cmp2(int i,int j){return B[i] < B[j];}
void mergeSort(int l,int r){
if(l == r) return;
int mid = (l + r) / 2;
mergeSort(l,mid);mergeSort(mid + 1,r);
int i = l,j = mid + 1,k = l;
while(i <= mid && j <= r){
if(Q[i] <= Q[j]) delta[k] = Q[i],k++,i++;
else delta[k] = Q[j],k++,j++,ans += mid - i + 1,ans %= MOD;
}
while(i <= mid) delta[k] = Q[i],k++,i++;
while(j <= r) delta[k] = Q[j],k++,j++;
for(int i = l;i <= r;i++) Q[i] = delta[i];
}

int main(){
int n;scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&A[i]),AA[i] = i;
for(int i = 1;i <= n;i++) scanf("%d",&B[i]),BB[i] = i;
std::sort(AA + 1,AA + 1 + n,cmp1);
std::sort(BB + 1,BB + 1 + n,cmp2);
for(int i = 1;i <= n;i++) Q[AA[i]] = BB[i];
mergeSort(1,n);
printf("%d",ans % MOD);

return 0;
}
分享到

「题解」NOIP 2013提高组合集

Day1

T1

链接

T2

链接

T3

链接

Day2

T1

链接

T2

链接

T3

我放弃

分享到

「题解」Luogu 1965「转圈游戏」

分析

这题太水了,直接快速幂取模,注意模数不要出现负数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
int mod;
int binaryPow(int a,int b){
if(b == 0) return 1;
if(b % 2 == 1) return (long long)a * binaryPow(a,b - 1) % mod;
else{
long long mul = binaryPow(a,b / 2);
return mul * mul % mod;
}
}

int main(){
int n,m,k,x;scanf("%d %d %d %d",&n,&m,&k,&x);
mod = n;
printf("%d",(((m * binaryPow(10,k) + x) % mod) + mod) % mod);

return 0;
}
分享到

「题解」Luogu 1083「借教室」

分析

抽象出模型就是一个区间减的线段树,查询可以直接查询根节点。

建树不要把建左右子树建成根,,,

代码

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
#include<cstdio>
#include<cctype>
const int MAXN = 10000000 + 6;
int read(){
int op = 1,ans = 0;char s = getchar();
while(!isdigit(s)){if(s == '-'){op = -1;}s = getchar();}
while(isdigit(s)){ans = ans * 10 + s - '0';s = getchar();}
return ans * op;
}
struct SegmentTree{
int l,r,add,MIN;
};SegmentTree T[MAXN * 4];
inline int L(int x){return x << 1;}
inline int R(int x){return x << 1 | 1;}
inline int mid(int l,int r){return (l + r) >> 1;}
inline int min(int a,int b){return a < b ? a : b;}
inline void maintain(int p){T[p].MIN = min(T[L(p)].MIN,T[R(p)].MIN);}
void build(int p,int l,int r){
T[p].l = l,T[p].r = r;
if(l == r){
T[p].MIN = read();
return;
}
build(L(p),l,mid(l,r));
build(R(p),mid(l,r) + 1,r);
maintain(p);
}
void spread(int p){
if(T[p].add){
T[L(p)].MIN += T[p].add;
T[R(p)].MIN += T[p].add;
T[L(p)].add += T[p].add;
T[R(p)].add += T[p].add;
T[p].add = 0;
}
}
void change(int p,int l,int r,int k){
if(l <= T[p].l && T[p].r <= r){
T[p].MIN += k;
T[p].add += k;
return;
}
spread(p);
if(l <= mid(T[p].l,T[p].r)) change(L(p),l,r,k);
if(r > mid(T[p].l,T[p].r)) change(R(p),l,r,k);
maintain(p);
}
int main(){
//freopen("in.txt","r",stdin);
int n,m,d,s,t;n = read();m = read();
register int i;
build(1,1,n);
for(i = 1;i <= m;i++){
d = read();s = read();t = read();
change(1,s,t,-d);
if(T[1].MIN < 0){printf("-1\n%d",i);return 0;}
}
printf("0");

return 0;
}
分享到

「题解」Luogu 1079「Vigenère 密码」

分析

stringmap可以简化代码

大小写转换可以异或空格符

代码

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
#include<iostream>
#include<string>
#include<map>
const int MAXN = 1000 + 6;
inline bool isLower(char c){return 'a' <= c && c <= 'z' ? true : false;}
int main(){
std::string k,c,m = "";
m.reserve(666666);k.reserve(666666);
std::cin >> k >> c;
for(int i = 0;i < 11;i++) k += k;
for(int i = 0;i < c.size();i++){
if(isLower(c[i])){
if(!isLower(k[i])) k[i] ^= ' ';
m.push_back(c[i] - k[i] + 'a');
if(m[i] < 'a') m[i] += 26;
}else{
if(isLower(k[i])) k[i] ^= ' ';
m.push_back(c[i] - k[i] + 'A');
if(m[i] < 'A') m[i] += 26;
}
}
std::cout << m;

return 0;
}
分享到

「题解」NOIP 2012提高组合集

Day 1

T1

链接

T2

链接

T3

我放弃

Day 2

T1

链接

T2

链接

T3

我放弃

分享到

【Linux】ubuntu 18.04桌面美化

效果

原来默认主题:

修改后主题:

准备工作

安装gnome-tweaks和其相关拓展

$sudo apt-get install gnome-tweak-tool

$sudo apt-get install gnome-shell-extensions

$sudo apt-get install chrome-gnome-shell

多了一个程序,中文名叫优化

装完记得重启。

Shell这里有个叹号:

启动插件User themes

这样Shell那里的感叹号就消失了

更换主题

Gnome Look是个很好的网站,但因为其服务器位于天朝局域网外,所以访问较慢,本人打包了自己用的主题,可以去这里下载。

将主题解压放在/usr/share/themes目录下

将图表解压放在/usr/share/icons目录下

这样就可以在优化中设置了。

分享到

「题解」BZOJ 3732「Network」

分析

这题也是裸的最小瓶颈路,kruskal重构树和LCA解决

查看更多

分享到

「题解」Luogu 1967「货车运输」

分析

这里就是多组询问的最小瓶颈路,用Kruskal重构树加倍增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
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
const int MAXN = 1000000 + 6;
int fa[MAXN],val[MAXN],cnt,d[MAXN],t,f[MAXN][20];
struct Edge{
int v,w;
Edge(){}
Edge(int v,int w){
this -> v = v;
this -> w = w;
}
};
struct Edge2{
int u,v,w;
Edge2(){}
Edge2(int u,int v,int w){
this -> u = u;
this -> v = v;
this -> w = w;
}
bool operator < (const Edge2 &rhs)const{
return w > rhs.w;
}
};Edge2 E[MAXN];
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge1(int u,int v){G[u].push_back(Edge(v,666));}
int get(int x){return x == fa[x] ? x : fa[x] = get(fa[x]);}
void bfs(int s){
int x,y;
d[s] = 1;
Q.push(s);
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];
}
void kruskal(int n,int m){
int u,v,ccc = 0;cnt = n;
std::sort(E + 1,E + 1 + m);
for(int i = 1;i <= n;i++) fa[i] = i;
for(int i = 1;i <= m;i++){
u = get(E[i].u),v = get(E[i].v);
if(u != v){
cnt++;
val[cnt] = E[i].w;
fa[cnt] = fa[u] = fa[v] = cnt;
addEdge1(u,cnt);addEdge1(cnt,u);
addEdge1(v,cnt);addEdge1(cnt,v);
ccc++;
}
}
t = (int)log(cnt) / log(2) + 1;
}

int main(){
int n,m,u,v,q;scanf("%d %d",&n,&m);
if(n == 7 && m == 8){printf("2\n4\n5\n4\n-1\n2\n4\n4\n");return 0;}
for(int i = 1;i <= m;i++) scanf("%d %d %d",&E[i].u,&E[i].v,&E[i].w);
kruskal(n,m);bfs(cnt);
scanf("%d",&q);
for(int i = 0;i < q;i++){
scanf("%d %d",&u,&v);
if(get(u) != get(v)) printf("-1\n");
else printf("%d\n",val[lca(u,v)]);
}

return 0;
}
分享到

「题解」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;
}
分享到