poj1330Nearest Common Ancestors 1470 Closest Common Ancestors（LCA算法）
LCA思想：http://www.cnblogs.com/hujunzheng/p/3945885.html
在求解最近公共祖先为问题上，用到的是Tarjan的思想，从根结点开始形成一棵深搜树，非常好的处理技巧就是在回溯到结点u的时候，u的子树已经遍历，这时候才把u结点放入合并集合中，
这样u结点和所有u的子树中的结点的最近公共祖先就是u了，u和还未遍历的所有u的兄弟结点及子树中的最近公共祖先就是u的父亲结点。以此类推。。这样我们在对树深度遍历的时候就很自然的将树中的结点分成若干的集合，两个集合中的所属不同集合的任意一对顶点的公共祖先都是相同的，也就是说这两个集合的最近公共最先只有一个。对于每个集合而言可以用并查集来优化，时间复杂度就大大降低了，为O(n + q)，n为总结点数，q为询问结点对数。/*题意很明显，就是求LCA!
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 10005
using namespace std;int n;
int x, y;
vector<int>g[N];
int f[N];
int vis[N], cnt[N];
int ret;int getFather(int x){return x==f[x] ? x : f[x]=getFather(f[x]);
}bool LCA(int u){vis[u]=1;f[u]=u;int len=g[u].size();if(u==x && vis[y]){ret=getFather(y);return true;}else if(u==y && vis[x]){ret=getFather(x);return true;}for(int i=0; i<len; ++i){int v=g[u][i];if(!vis[v]){if(LCA(v)) return true;f[v]=u;}}return false;
}int main(){int t;scanf("%d", &t);while(t--){scanf("%d", &n);memset(cnt, 0, sizeof(cnt));for(int i=1; i<n; ++i){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);++cnt[v];}memset(vis, 0, sizeof(vis));scanf("%d%d", &x, &y);for(int i=1; i<=n; ++i)if(cnt[i]==0){LCA(i);break;}printf("%d\n", ret);for(int i=1; i<=n; ++i)g[i].clear();}return 0;
}#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 905
#define M 25000
using namespace std;vector<int>g[N];
vector<int>p[M];
int cnt[N];
int f[N];
int vis[N];
int ans[N];int n, m;int getFather(int x){return x==f[x] ? x : f[x]=getFather(f[x]);
}void LCA(int u){f[u]=u;vis[u]=1;int len;len=p[u].size();for(int i=0; i<len; ++i){int v=p[u][i];if(vis[v])++ans[getFather(v)];}len=g[u].size();for(int i=0; i<len; ++i){int v=g[u][i];if(!vis[v]){LCA(v);f[v]=u; }}
}int main(){while(scanf("%d", &n)!=EOF){memset(cnt, 0, sizeof(cnt));for(int i=1; i<=n; ++i){vis[i]=0;ans[i]=0;int a, d, b;char ch;scanf("%d", &a);while(scanf("%c", &ch) && ch!='(');scanf("%d", &d);while(scanf("%c", &ch) && ch!=')');while(d--){scanf("%d", &b);++cnt[b];g[a].push_back(b);}}scanf("%d", &m);while(m--){char ch;while(scanf("%c", &ch) && ch!='(');int u, v;scanf("%d%d", &u, &v);p[u].push_back(v);p[v].push_back(u);while(scanf("%c", &ch) && ch!=')');}for(int i=1; i<=n; ++i)if(cnt[i]==0){LCA(i);break;}for(int i=1; i<=n; ++i)if(ans[i]!=0)printf("%d:%d\n", i, ans[i]);for(int i=1; i<=n; ++i)g[i].clear(), p[i].clear();}return 0;
}相关文章：
干货 | 时间序列预测类问题下的建模方案探索实践
作者 | 陆春晖责编 | Carol出品 | AI科技大本营（ID:rgznai100）背景时间序列类问题是数据分析领域中一类常见的问题，人们有时需要通过观察某种现象一段时间的状态，来判断其未来一段时间的状态。而时间序列就是该种现象某一个统计指…
Redis安装与源码调试
linux版本：64位CentOS 6.5 Redis版本：redis-3.0.6 (更新到2016年1月22日) Redis官网：http://redis.io/ Redis常用命令：http://redis.io/commands 1.安装Redis # wget http://download.redis.io/releases/redis-3.2.6.tar.g…
system pause in C#
方法一： Console.Write("Press any key to continue . . . "); Console.ReadKey(true); 注：也可用ReadLine()或Read()，但是只能对回车进行响应，不能达到anykey的效果。 方法二： 1) 在源文件using处加入using…
C#设置当前程序通过IE代理服务器上网
注意：以下设置只在当前程序中有效，对IE浏览器无效，且关闭程序后，自动释放代码。 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Runtime.InteropServices;public static …
计算机科学精彩帖子收集
linux源码 LXR 源自“the Linux Cross Referencer”，中间的“X”形象地代表了“Cross”。与 Source Navigator 类似，它也是分析阅读源代码的好工具。不同的是，它将源代码借助浏览器展示出来，文件间的跳转过程成了我熟悉的点击超链…
挑战王者荣耀“绝悟” AI，我输了！
作者 | 马超责编 | 伍杏玲出品 | CSDN（ID：CSDNnews）腾讯 AI Lab 与王者荣耀联合研发的策略协作型AI，“绝悟”首次开放大规模开放：5月1日至4日，玩家从王者荣耀大厅入口，进入“挑战绝悟”测试&…
java 注解类说明
一、类中注解 SuppressWarnings ("serial"); 关键字 用途deprecation使用了不赞成使用的类或方法时的警告unchecked执行了未检查的转换时的警告，例如当使用集合时没有用泛型 (Generics) 来指定集合保存的类型。fallthrough当 Switch 程序块直接通往下一种…
《ArcGIS Runtime SDK for Android开发笔记》——（13）、图层扩展方式加载Google地图...
1、前言 http://mt2.google.cn/vt/lyrsm225000000&hlzh-CN&glcn&x420&y193&z9&sGalil 通过图层扩展类的方式加载Google地图的是我们通常获取Google地图的一种方式，根据这种方式我们可以通过拼接地图瓦片Url字符串获取瓦片数据，关…
调试JDK源码-一步一步看HashMap怎么Hash和扩容
调试JDK源码-一步一步看HashMap怎么Hash和扩容 调试JDK源码-ConcurrentHashMap实现原理 调试JDK源码-HashSet实现原理 调试JDK源码-调试JDK源码-Hashtable实现原理以及线程安全的原因 还是调试源码最好。 开发环境 JDK1.8NetBeans8.1 说明：调试HashMap的 publ…
开源一年，阿里轻量级AI推理引擎MNN 1.0.0正式发布
在经过充分的行业调研后，阿里淘系技术部认为当时的推理引擎如TFLite不足以满足手机淘宝这样一个亿级用户与日活的超级App。于是，他们从零开始自己搭建了属于阿里巴巴的推理引擎MNN。1年前，MNN在Github上开源，截止目前获得了3.9k S…
人生在成败中进步
参考文献《佛经》 人生在成败中进步佛经中有云：“菩萨者，福慧深利，道观双流。”“福慧双修”、“福慧双全”是众生成佛的必由之道，也是众生修行的理想追求。人生中，虽然不可能人人都能成佛，但是佛经有云&am…
【原】YUI压缩与CSS media queries下的bug
大概是上个月，使用YUI压缩一个css文件后，发现只要是被压缩后的css文件有部分根本无法工作，一直都不知啥问题引起的，让我感到头疼。 今天发现了只要是在媒体查询中的样式无法起作用，于是才开始怀疑是media被压缩后引起的…
Spring源码分析【4】-Spring扫描basePackages注解
org.springframework.beans.factory.support.DefaultListableBeanFactory 重要数据结构 /** Map of bean definition objects, keyed by bean name */private final Map<String, BeanDefinition> beanDefinitionMap new ConcurrentHashMap<String, BeanDefinition&…
c语言c++语言中静态变量，函数详解
静态变量，静态函数对于一些c，c的初学者来说，造成了不少的困扰。昨晚和寝室的室友讨论到这 个问题，想了一下，作了一下总结：虽然说c和c在很多人的眼里就是孪生姐妹，其实还是有很大区别的。在这里分…
深度解析MegEngine亚线性显存优化技术
基于梯度检查点的亚线性显存优化方法[1]由于较高的计算/显存性价比受到关注。MegEngine经过工程扩展和优化，发展出一套行之有效的加强版亚线性显存优化技术，既可在计算存储资源受限的条件下，轻松训练更深的模型，又可使用更大batch…
2016-04-28
2019独角兽企业重金招聘Python工程师标准>>> 1.提交form表单之前的函数(校验不错):onsubmit"return A();".2.解析XML的方式:2.1.DOM是用与平台和语言无关的方式表示XML文档的官方W3C标准,基于"树"(DocumentBuilderFactory).2.2.SAX的优点类似于…
Spring源码分析【8】-MyBatis注解方法不能重载
代码如下： 这是不可以的，会报错： 2016-08-18 11:36:00,267 [main] ERROR [org.mybatis.spring.mapper.MapperFactoryBean] - Error while adding the mapper interface com.unix21.mapper.UserMapper to configuration.java.lang.IllegalArgu…
不知道这 7 大 OpenCV 函数怎么向计算机视觉专家进阶？
作者 | Lazar Gugleta译者 | Arvin，责编 | 夕颜头图 | CSDN付费下载自视觉中国出品 | CSDN（ID:CSDNnews）计算机视觉和计算机图形学现在非常流行，因为它们与人工智能息息相关，它们主要的共同点是使用同一个OpenCV库&…
MySQL5.5复制新特性
MySQL5.5复制新特性一.MySQL5.5复制改进MySQL5.5版本对MySQL Replication进行了多项的改良，以提供数据的完整性，性能和应用灵活性更高水平。1.Semisynchronous Replication：主从之间的等待机制2.Slave fsync tuning:调整slave fsync包括sync-…
GitLab 8.7发布
日前，GitLab 8.7版发布。该版本中，添加了新功能和优化，并小幅提升了性能。\\8.7版本发布于8.6版本整整30天之后，跟上了每月22日次版本的进度。最新的版本增加了在单个问题上设置到期日期的支持以及以用户所在时区而不是UTC来显示所…
Java飞行记录器 JRockit Flight Recorder JFR诊断JVM的历史性能和操作
需要展开子树，复制堆栈跟踪，就可以查看到代码调用链，看到自己的业务代码，从而定位到最耗时的代码位置：
vi/vim: 使用taglist插件
本节所用命令的帮助入口： :help helptags :help taglist.txt 上篇文章介绍了在vim中如何使用tag文件，本文主要介绍如何使用taglist插件(plugin)。 想必用过Source Insight的人都记得这样一个功能：SI能够把当前文件中的宏、全局变量、函数等t…
学会这些Python美图技巧，就等女朋友夸我了
来源 | ZackSock（ID: ZackSock）Python中有许多用于图像处理的库，像是Pillow，或者是OpenCV。而很多时候感觉学完了这些图像处理模块没有什么用，其实只是你不知道怎么用罢了。今天就给大家带了一些美图技巧，让…
Linux下的softlink和hardlink（转）
Linux中包括两种链接：硬链接(hard link)和软链接(soft link)，软链接又称为符号链接（symbolic link）创建命令：ln -s destfile/directory softlink #建立软连接 ln destfile hardlink #建立硬连接in…
ubuntu安装之后的最初几天一路杂记
我就随便写了啊，没那么正式，想到什么就写什么。 由于大四的毕业设计要做一个牵扯到linux的项目，最近不得不再次玩起了ubuntu，其实前一次（大二的时候吧）就已经在电脑上安装过一个ubuntu了，只不过…
百万级访问量网站的技术准备工作[转帖]
当今从纯网站技术上来说，因为开源模式的发展，现在建一个小网站已经很简单也很便宜，所以很多人都把创业方向定位在互联网应用。这些人里大多数不是 很懂技术，或者不是那么精通，而网站开发维护方面的知识又很分散&#x…
智能驾驶L2的黄金时代，打磨地图是关键
作者 | 自动驾驶从业者，中寰卫星黄亮出品 | AI科技大本营（ID:rgznai100）智能驾驶L2，以我们通俗的定义是，以高级辅助驾驶的产品为主的各种巡航产品，包括定速巡航，自适应巡航ACC，预见性…
css中的垂直居中方法
单行文字 （外行高度固定） line-height 行高， 将line-height值与外部标签盒子的高度值设置成一致就可以了。 height:3em; line-height:3em; 多行文字 图文结合（图和单行文字） 图文结合（图和多行文字…
U盘挂载，gedit,vi,文本模式中文乱码等等问题
U盘或硬盘挂载 首先，我们要查看一下磁盘的分区信息sudo fdisk -l (注意注意，是小写的L，不是1，也不是i） 这里可以看到我的硬盘情况，前面几个是win7系统下的C,D ,E ,F 盘。我现在是在图书馆，没…
一次对语音技术的彻底批判
作者 | Alexander Veysov译者 | 孙薇，编辑 | 夕颜出品 | AI科技大本营（ID：rgznai100）ImageNet的出现带来计算机视觉领域的突破发展，掀起了一股预训练之风，这就是所谓的ImageNet时刻。但与计算机视觉同样重要…