HDU 5606 tree 并查集

时间:2022-09-20 19:50:04

tree

把每条边权是1的边断开,发现每个点离他最近的点个数就是他所在的连通块大小.

开一个并查集,每次读到边权是0的边就合并.最后Ans​i​​=size[findset(i)],size表示每个并查集根的size

Ans_i=size[findset(i)],sizeAns​i​​=size[findset(i)],size表示每个并查集根的sizesize.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn=+;
int a[maxn];
int fa[maxn];
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
memset(a,,sizeof(a));
for(int i=; i<=n; ++i)
fa[i]=i;
for(int i=; i<n; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(w==)
{
int fx=find(u);
int fy=find(v);
if(fx==fy)continue;
fa[fy]=fx;
}
}
for(int i=; i<=n; i++)
{
int f=find(i);
a[f]++;
}
int ans=;
for(int i=; i<=n; i++)
{
ans=(ans^a[fa[i]]);
}
printf("%d\n",ans);
}
return ;
}

HDU 5606 tree 并查集的更多相关文章

  1. Hdu&period;1325&period;Is It A Tree&quest;&lpar;并查集)

    Is It A Tree? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) To ...

  2. hdu 1325 Is It A Tree&quest; 并查集

    Is It A Tree? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Tot ...

  3. tree&lpar;并查集&rpar;

    tree Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submis ...

  4. HDU 2818 &lpar;矢量并查集&rpar;

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2818 题目大意:每次指定一块砖头,移动砖头所在堆到另一堆.查询指定砖头下面有几块砖头. 解题思路: ...

  5. Is It A Tree&quest;&lpar;并查集&rpar;

    Is It A Tree? Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 26002   Accepted: 8879 De ...

  6. CF109 C&period; Lucky Tree 并查集

    Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal re ...

  7. &lbrack;Swust OJ 856&rsqb;--Huge Tree&lpar;并查集&rpar;

    题目链接:http://acm.swust.edu.cn/problem/856/ Time limit(ms): 1000 Memory limit(kb): 10000 Description T ...

  8. Codeforces Round &num;363 &lpar;Div&period; 2&rpar;D&period; Fix a Tree&lpar;并查集&rpar;

    D. Fix a Tree time limit per test 2 seconds memory limit per test 256 megabytes input standard input ...

  9. Is It A Tree&quest;&lpar;并查集&rpar;(dfs也可以解决)

    Is It A Tree? Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u Submi ...

随机推荐

  1. zTree树的模糊搜索

    工作需要,所以做了一个比较方便的搜索功能:1.功能实现都是基于zTree的API:2.如有更好的建议,欢迎拍我:其中要说明下的是flag 这个字段, 这是我自己定义的扩展字段,代码中涉及到flag 请 ...

  2. Mysql命令行中文乱码的解决方法

    环境:Windows 8 64位,Mysql  5.0.96 for Win64 (x86) 数据库本身安装时默认已经是使用utf8编码的了,但在命令行中执行查询时,查询到的中文依然乱码,解决方法如下 ...

  3. &OpenCurlyDoubleQuote;Request Entity Too Large” 上传图片出现大小限制

    昨天公司安卓app上传了图片爆了下面这个错误 <"-//IETF//DTD HTML 2.0//EN"> <html><head> <ti ...

  4. Azure HDInsight HBase DR解决方案

    Sun wei  Sat, Feb 28 2015 3:07 AM Apache HBase是目前非常流行的NoSQL数据库,通过HDFS+Zookeep+Master+Region Server的架 ...

  5. Apache配置HTTPS协议搭载SSl配置全过程

    1.首先要开启相应的扩展和辅助的dll(ssleay32.dll,libeay32.dll)到system32下 2.生成服务器证书 安装好在bin目录下有一个openssl.exe文件,用来生成证书 ...

  6. css选择表格偶数行

    css代码tr:nth-child(even){background:gray} 选择偶数行 tr:nth-child(even){background:gray} 选择奇数行  

  7. 1&period;2 N层架构

    N层架构 介绍 ABP架构 其他(通用) 领域层 应用层 基础设施层 网络和展现层 其他 总结 介绍 应用程序代码库的分层架构是被广泛认可的可以减少程序复杂度.提高代码复用率的技术.为了实现分层架构, ...

  8. 三方面搞定http协议之&OpenCurlyDoubleQuote;状态码”

    当我们向服务器请求数据的时候,服务器会给我们一个反馈,告诉我们对待我们的请求,服务器处理得怎么样了,而这个反馈,是通过数字来传达的,这个数字就叫状态码. 状态码分为以下几种: 1xx:指示信息--表示 ...

  9. 随心测试&lowbar;数据库&lowbar;003 &lt&semi;数据库存储结构&gt&semi;

    接上篇:了解了_数据库系统组成,继续理解必备知识点:数据库存储_逻辑结构 快速理解 数据存储结构:数据库系统_数据库_表 1. 理解什么是数据库 数据库发展:大致由 人工管理.文件系统.数据库系统(高 ...

  10. 分享一个好用的tmux配置文件

    tmux众所周知,不过多介绍,友好的tmux配置,让人用起来很舒服,分享一个tmux配置文件 # ------ general ------------------------------------ ...