ICPC入门尝试周总结篇（五）

这周主要还是学习了有关搜索的题目，但搜索可以涉及很多别的知识点以及算法，所以另外也看了一些相关的文章，看的文章也很杂，比如，知道了全局变量和静态变量不用手动赋初值为0，它的默认值就是0，比如，freopen，便于在线下多次调试程序的时候方便，直接自己读取文件，也方便查看代码运行时间，比如，倍增法求LCA（最近公共祖先）、二叉查找树、再就是看了重载运算符和老师发的题了。

题并没有看多少，本来以为有了上周的铺垫，这周看起题来会有所简单，但搜索只是一种方法，每一篇题解都有作者的思想以及涉及到的更多的没有学过的知识，怎么说呢，就是，看是看了不少题，但真正看得懂的并没有多少，随着一篇篇题解的阅读，以及随带搜索百度有关的算法知识点，在这个过程中，我忽然发现，，，，，这其实并不是我想学的ACM，或者说，以前的我根本不了解ACM到底是什么，大学生程序设计大赛，我以为是编写程序，软件开发之类的东西，但其实，是解数学题..........我好鸡肋，我的数学并不好，前几天看的求LCA中有一种Tarjan算法和RMQ直接给我看崩，因为我自己并不是计算机本专业的，身在电子，最初的想法只是开拓一下自己的兴趣，当时的我只是对编程比较感兴趣，所以来尝试一下，后来发现oh my god，好难，而且我对数学着实没那么高的兴趣，所以这门课 的入门尝试怕是要以失败告终了。

虽然入门尝试失败，但这并不影响我应该安安心心完成这门选修课的进程，之后会继续认真听老师讲课，增加自己的知识储量，努力顺利完成这门选修课。

记录一个为数不多的这周看懂的题：

[JLOI2009]二叉树问题 - 洛谷

解 ：

#include
#include
#include
#include
#include
using namespace std;

int n;
int fa[101],root[101],son[101];

int depth[101],width[101];
int lca(int x,int y){
	if(x == y){
		return x;
	}
	else if(depth[x] == depth[y]){  //注意深度是从上往下看的
		return lca(fa[x],fa[y]);  //如果两个结点相同 则访问他们的父亲节点 直到二者相同
	}
	else if(depth[x] < depth[y]){  //如果第二个比第一个深就将深的上移 因为他们可能会在同一条枝上
		return lca(x,fa[y]);
	}
	else{
		return lca(fa[x],y);  //同上同理
	}
}

int main(){
	cin >> n;  //输入n个结点
	depth[1] = 1;   //默认根节点深度为1
	for(int i = 1;i < n;i++){
		cin >> root[i] >> son[i];  //每一组数据都是由根节点指向子节点
		depth[son[i]] = depth[root[i]] + 1;   //子节点的深度是父亲节点深度+1
		fa[son[i]] = root[i];  //每一个子节点的父亲节点都是对应的根节点
	}
	int x,y;
	cin >> x >> y;  //输入所求的两个结点
	int max_depth = 1;   //初始化最大深度为1
	for(int i = 1;i <= n;i++){
		max_depth = max(max_depth,depth[i]);
		width[depth[i]]++;   //这个很巧妙每有一个结点需要记录深度，深度相同的话 该层上宽度就加一
	}
	cout << max_depth << endl;
	int max_width = 1;   //初始化最大宽度为1
	for(int i = 1;i <= n;i++){
		max_width = max(max_width,width[i]);  
	}
	cout << max_width << endl;
	int k = lca(x,y);      //求 LCA 的结点序号
	cout << (depth[x] - depth[k]) * 2 + depth[y] - depth[k];      //求距离
	return 0;
}