COGS 2089. 平凡的测试数据
【题目描述】
树链剖分可以干什么?
“可以支持在树中快速修改一个点信息,快速询问一条链信息”
LCT可以干什么?
“可以支持树链剖分支持的特性,并且支持快速链接两个棵树,或者断开某条边”
那我现在要出一道关于树的题目,一开始有n个点,每个点自成一颗树,所以现在有n棵树。每个点有一个权值。有以下这些操作类型:
连接操作:1 a b,连接a和b,使a成为b的儿子结点,a一定是某个树的根节点。这样就把两个数连接到一起,此时a以及所有后代的根节点均为b所在树的根节点。
询问操作:2 a,询问a到自己所在树的根节点所有在路径(包括自己和根节点)上的所有点的权值的异或和。
恩...但是由于我懒,所以还没有造数据,请你帮我写个标程让我用来造数据吧。
【输入格式】
第一行两个整数n和m,表示有n个点和m个操作。
接下有一行n个整数,第i个整数表示第i个点的权值。
接下来m行,每行为三个整数1 a b,或者2 a。
如果是1 a b表示这是一个连接操作,意义见题目。
如果是2 a表示这是一个询问操作,意义见题目。
【输出格式】
对于每个询问操作,输出一行,表示从a到根节点路径上所有点的权值的异或和。
【样例输入】
5 8
1 2 3 4 5
2 2
1 2 1
2 2
1 4 3
1 3 2
2 3
1 5 1
2 5
【样例输出】
2
3
0
4
【提示】
样例解释
样例中每个节点权值与标号相同
第一个询问中2的根节点是自己,所以第一个询问2节点的答案为0
第二个询问中2的根节点是1,路径为2-1,所以答案为2 xor 1 = 3
第三个询问中3到根节点的路径为3-2-1,所以答案为3 xor 2 xor 1 = 0
第四个询问中5到根节点的路径为5-1,所以答案为5 xor 1 = 4
数据范围
对于40%的数据1 <= n,m <= 1000
对于90%的数据1 <= n <= 100000, 1 <= m <= 200000
对于100%的数据1 <= n <= 300000, 1 <= m <= 500000
所有节点的权值均为正整数且在int范围内
题解:
带权并查集,考试的时候没想出出来,真是脑抽,为什么可以用并查集呢?因为他只要维护路径上的总和,并且刚好也只有合并和查询两个操作,不过主要还是因为只有维护路径上的信息。
具体怎么做?可以考虑将点权付给边权。记s[i]表示i节点到根节点的亦或合,然后每次合并两棵树时只要将被合并的点的点权付给边权即s[x]=quan[x];(quan[x]是点权),合并路径是只要将两段路径抑或起来就可以了。即s[now]=s[now]^s[fa[now]],最后因为是边权,没有算根节点,输出答案时在亦或一下就可以了。
代码:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define ll long long
#define MAXN 100010
#define MAXN2 500000
using namespace std;
int quan[MAXN2*],s[MAXN2*],fa[MAXN2*];
int n,m,num=,hhh; int find(int now){
if(fa[now]!=now) hhh=find(fa[now]);
else hhh=fa[now];
s[now]=s[now]^s[fa[now]];
fa[now]=hhh;
return fa[now];
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) {
scanf("%d",&quan[i]);
fa[i]=i;
}
for(int i=;i<=m;i++){
int id,x,y;
scanf("%d",&id);
if(id==){
scanf("%d",&x);
int hh=find(x);
printf("%d\n",s[x]^quan[hh]);
}
else{
scanf("%d%d",&x,&y);
fa[x]=y;
s[x]=quan[x];
}
}
return ;
}
最新文章
- linux系统性能调优第一步——性能分析(vmstat)
- jquery选择器中两个class是什么意思?
- windbg内核诊断方式--转载
- Entity Framework学习笔记(六)----使用Lambda查询Entity Framework(1)
- EXTJS4.2 chart 柱状图
- Java中的比较
- 在Android应用程序使用YouTube API来嵌入视频
- 转:enum与typedef enum的用法
- Codeforces Round #235 (Div. 2) D. Roman and Numbers (数位dp、状态压缩)
- hibernate系列笔记(2)---Hibernate的核心API
- 如何编写高效的SQL
- jquery Dialog弹框插件
- 实验八 Web基础 SQL注入原理
- checkpoint防火墙SmartDashboard登录出错
- VC++ 字符串Dword、LPSTR、LPWSTR、LPCSTR、LPCWSTR、LPTSTR、LPCTSTR
- wc语法2
- [转帖]新的Linux后门开始肆虐 主要攻击中国服务器
- Python Cookbook 笔记--12章并发编程
- socket编程基础-字节序/IP/PORT转换/域名
- Date 当前程序日期格式 参数设置 DecimalSeparator