做什么题都要注意数组的大小，不要犯下数组越界的错误（温馨（狠心）提示）；
做了好多遍就是不对，原来是【20】的数组，在for下循环1——》20，神奇爆零；
链接：https://www.luogu.org/problemnew/show/p3398
这道题有一个性质：
判断树上两条路径是否有交点或重叠部分，那就是
有a,b一条路径，还有c,d这条路径。
要是这两条路径相交或重合，
那么要不是lca(a,b)在cd上，就是lca(c,d)在ab上；
显然易得啊（反正我是不会证明，背下来记好了）；
倍增lca
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=2000050; int pre[maxn],other[maxn],last[maxn],l; int n,q; void add(int x,int y) { l++; pre[l]=last[x]; last[x]=l; other[l]=y; } int dep[maxn],jump[maxn][20]; void dfs(int u) { for(int p=last[u];p;p=pre[p]) { int v=other[p]; if(v==jump[u][0]) continue; dep[v]=dep[u]+1; jump[v][0]=u; dfs(v); } } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=0;i<=17;i++) { if((dep[u]-dep[v])&(1<<i)) u=jump[u][i]; } if(u==v) return u; for(int j=17;j>=0;j--) { if(jump[u][j]!=jump[v][j]) { u=jump[u][j]; v=jump[v][j]; } } return jump[u][0]; } int main() { scanf("%d%d",&n,&q); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs(1); for(int j=1;j<=17;j++)//17就够了，不要搞什么20 { for(int i=1;i<=n;i++) { jump[i][j]=jump[jump[i][j-1]][j-1]; } } for(int i=1;i<=q;i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); int x=lca(a,b); int y=lca(c,d); int l1=dep[a]+dep[b]-2*dep[x];//a->b路径长度 int l2=dep[c]+dep[d]-2*dep[y];//c->d路径长度 if(dep[c]+dep[x]-2*dep[lca(x,c)]+dep[d]+dep[x]-2*dep[lca(x,d)]==l2)//c->x->d==l2 { printf("yn"); continue; } if(dep[a]+dep[y]-2*dep[lca(a,y)]+dep[b]+dep[y]-2*dep[lca(y,b)]==l1)//a->y->b==l1,就是两条线段长度和等于整个线段长度 { printf("yn"); continue; } printf("nn"); } return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/602971.html