skkyk:题解 洛谷P2420 【让我们异或吧】lca+xor…
2019-08-16 07:46:05来源:博客园 阅读 ()
skkyk:题解 洛谷P2420 【让我们异或吧】lca+xor前缀和
刚学了LCA,写篇题解巩固一下
首先题目有误: (A是否是男生 )xor( B是否是男生)=A和B是否能够成为情侣,这句话显然是错误的qwq
对于这道题,容易看出,对于待处理的两个点,只要我们找到他的最近公共祖先,问题便游刃而解了
所以我的思路就是:lca+xor前缀和
这是我的大法师函数
yihuo数组就是保存当前节点到根节点的xor值
推算了一下,对于xor前缀和有: 两个点x,y间的的xor值=yihuo[x]^yihuo[y]
void dfs(int f,int father,int XOR)
{
depth[f]=depth[father]+1;
fa[f][0]=father;
yihuo[f]=XOR;
for(int i=1;(1<<i)<=depth[f];i++)
fa[f][i]=fa[fa[f][i-1]][i-1];
for(int i=head[f];i;i=edge[i].next)
if(edge[i].to!=father)
dfs(edge[i].to,f,XOR^edge[i].dis);
}
剩下的就是普通的lca,在深层节点向上跳的每个过程中
记录下待求的ans
具体实现见代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,cnt,ans;
#define N 100000+1
int fa[N][22];
struct node {
int next,to,dis;
} edge[N<<1];
int head[N],yihuo[N],lg[N],depth[N],a[N];
inline void add(int from,int to,int dis) {
edge[++cnt].to=to;
edge[cnt].next=head[from];
edge[cnt].dis=dis;
head[from]=cnt;
}
void dfs(int f,int father,int XOR) {
depth[f]=depth[father]+1;
fa[f][0]=father;
yihuo[f]=XOR;
for(int i=1; (1<<i)<=depth[f]; i++)
fa[f][i]=fa[fa[f][i-1]][i-1];
for(int i=head[f]; i; i=edge[i].next)
if(edge[i].to!=father)
dfs(edge[i].to,f,XOR^edge[i].dis);
}
void lca(int x,int y) {
if(depth[x]<depth[y])
swap(x,y);
while(depth[x]>depth[y]) {
ans=ans xor yihuo[x] xor yihuo[fa[x][lg[depth[x]-depth[y]]-1]];
x=fa[x][lg[depth[x]-depth[y]]-1];
}
if(x==y)
return ;
for(int i=lg[depth[x]]-1; i>=0; i--) {
if(fa[x][i]!=fa[y][i]) {
ans=ans xor yihuo[x] xor yihuo[fa[x][i]];
ans=ans xor yihuo[y] xor yihuo[fa[y][i]];
x=fa[x][i],y=fa[y][i];
}
}
ans=ans xor yihuo[x] xor yihuo[y] ;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n-1; i++) {
int u,v,dis;
scanf("%d%d%d",&u,&v,&dis);
add(u,v,dis),add(v,u,dis);
}
for(int i=1; i<=n; i++)
lg[i]=lg[i>>1]+1;
dfs(1,0,0);
scanf("%d",&m);
for(int i=1,x,y; i<=m; i++) {
ans=0;
scanf("%d%d",&x,&y);
lca(x,y);
printf("%d\n",ans);
}
return 0;
}
留个赞再走吧qwq
原文链接:https://www.cnblogs.com/skkyk/p/11156383.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- 洛谷P1907口算练习题 2020-03-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash