这道题一开始以为是平衡树结果发现复杂度过不去,然后发现我们一直合并而且只是记录到最低的距离,那么就是带权并查集了,带权并查集的权一般是到根的距离,因为不算根要好打,不过还有一些其他的,具体的具体打。

#include <cstdio>
#include <cstring>
const int N=;
int h[N],f[N],size[N];
char s[];
inline int find(int x){
if(f[x]==x)return x;
int temp=f[x];f[x]=find(f[x]);
if(temp!=f[x])h[x]+=h[temp];
return f[x];
}
inline void Unit(int x,int y){
h[find(x)]=size[find(y)];
size[find(y)]+=size[find(x)];
f[find(x)]=find(y);
}
int main(){
int T,x,y;scanf("%d",&T);
for(int i=;i<N;i++)f[i]=i,size[i]=,h[i]=;
while(T--){
scanf("%s",s);
if(s[]=='M')scanf("%d%d",&x,&y),Unit(x,y);
else scanf("%d",&x),find(x),printf("%d\n",h[x]);
}
}

最新文章

  1. 如何发布一个Mac应用并使其成为全球付费榜第一
  2. tweenmax.js 文档
  3. Bootstrap 3 简介
  4. 【系统移植】Android系统移植
  5. [杂]SQL Server 之 Understanding Connection Pooling and Transactions
  6. getattr的作用是什么呢
  7. layer
  8. LINQ标准查询操作符(二)——Join、GroupJoin、GroupBy、Concat、
  9. strcpy函数导致release版程序崩溃
  10. Android 编程下的计时器
  11. 安装linux工作环境
  12. SpringMVC-HelloWorld (XML)
  13. linux发行版和内核的关系
  14. TensorFlow-相关 API(学习笔记 )
  15. Python中byte与str
  16. bash shell while语法
  17. Oracle 连接查询
  18. 用一句sql语句更新两个表并可更新对应的字段的值
  19. WEB学习笔记12-高可读性的HTML之如何正确设计表单
  20. SQL Server 异常解决:语句被终止。完成执行语句前已用完最大递归 100。

热门文章

  1. android 按钮动态点击
  2. FROM_UNIXTIME
  3. C# 隐藏窗口标题栏、隐藏任务栏图标
  4. go学习笔记-变量和常量
  5. 为什么我要放弃javaScript数据结构与算法(第一章)—— JavaScript简介
  6. 1 http协议
  7. 7 tftp
  8. 深度学习(deep learning)优化调参细节(trick)
  9. Python操作nosql数据库之redis
  10. Hibernate-ORM:03.Hibernate主键生成策略