刚学了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[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("%dn",ans); } return 0; }
留个赞再走吧qwq
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602787.html