zzq啊 真的很强 这道题是一个非常经典的问题吧 询问树上两条路径是否相交
慢着让我思维如此痛苦的题目 竟然被别人暴力A了？？？excuse me???
暴力先把两点之间的路径标记一下然后 跑另外两点之间的路径 看看是否有重合
然后树剖一下加线段树维护 竟然 竟然 暴力直接A 我是真的菜！！！树剖都不会。
我想了一晚上最后瞎写了一个算法然后一遍AC的经历是相当的精彩。其实我就是没有证明一个结论而已。
引理：树上两条路径如果相交则必然有两点的LCA在另两点的路径之间。
证明：利用反正法 两条路径之间是相交的 设 x为交点 x不是另外一组点对的LCA
因为 有 depth[LCA]>depth[x] x不是LCA 所以必然有LCA在x的上方 此时x还应在 当前点对的路径之上。
也就是说x有两个父亲 一个是LCA所在边 一个是那条路径上的一个点 此时 是不可能出现的情况 所以LCA和那个点重合 所以LCA在当前点对的路径上
如果x只有一个父亲LCA 这个x是那条路径上的终点呢 此时 x是那条路径上的LCA 然后x在当前的路径上
证毕。
我的做法是先判断这两个LCA 其中深度较深的是否可以跳到两个LCA之上 当然这个没有任何意义。
我们只需判断一个深度较深的LCA是否在相对的那一组点对的路径之上即可。
然后接下来我判断的步骤是 一个LCA 既然在另一组点的最短路上 那么这个LCA必然是两个LCA中深度最深的那个
考虑如何判断一条路径之中包含某点 我的做法是 必然次两点之中有一点能直接向上蹦到那个LCA处
我只需网上蹦即可 这样来判断 LCA是否在两点之上。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cmath> #include<cstdio> #include<ctime> #include<cstring> #include<string> #include<queue> #include<deque> #include<cmath> #include<cstdlib> #include<cctype> #include<utility> #include<vector> #include<algorithm> #include<set> #include<map> #include<bitset> #define INF 2147483646 #define up(p,i,n) for(int i=p;i<=n;++i) using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } inline void put(int x) { x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar(' ');return; } const int MAXN=100002; int n,m,len,T,h,t; int vis[MAXN],f[MAXN][21]; int lin[MAXN<<1],nex[MAXN<<1],ver[MAXN<<1]; int q[MAXN],depth[MAXN]; struct wy { int a,b,lca; }A,B,C; inline void add(int x,int y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } inline void bfs() { q[++t]=1;vis[1]=1;depth[1]=1; while(h++<t) { int te=q[h]; for(int i=lin[te];i;i=nex[i]) { int tn=ver[i]; if(vis[tn])continue; f[tn][0]=te; depth[tn]=depth[te]+1; for(int j=1;j<=T;++j)f[tn][j]=f[f[tn][j-1]][j-1]; vis[tn]=1;q[++t]=tn; } } return; } inline int LCA(int x,int y) { for(int i=T;i>=0;--i) if(depth[f[y][i]]>=depth[x])y=f[y][i]; if(x==y)return x; for(int i=T;i>=0;--i) if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } inline void swap1(wy &x,wy &y) { C=x;x=y;y=C; return; } inline int banlance(int x,int y) { for(int i=T;i>=0;--i) if(depth[f[y][i]]>=depth[x])y=f[y][i]; if(x==y)return 1; return 0; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); T=(int)(log(n*1.0)/log(2.0))+1; up(1,i,n-1) { int x,y; x=read();y=read(); add(x,y);add(y,x); } bfs(); for(int i=1;i<=m;++i) { int flag=0; A.a=read();A.b=read();B.a=read();B.b=read(); if(depth[A.a]>depth[A.b])swap(A.a,A.b);//在此定义depth[a]<=depth[b]; if(depth[B.a]>depth[B.b])swap(B.a,B.b); A.lca=LCA(A.a,A.b),B.lca=LCA(B.a,B.b); if(depth[A.lca]>depth[B.lca])swap1(A,B);//再次定义depth[A.lca]<=depth[B.lca]; if(banlance(B.lca,A.a)||banlance(B.lca,A.b))flag=1; if(flag)puts("Y"); else puts("N"); } return 0; }
其实还有更快的判断其中一点是否在一条路径之上。
当前LCA 这个点 距两点的距离之和 等于两点之间的距离。
由于这种方法还需要再求LCA 还没我的好 ！！
所以就不写了。真羡慕树剖套线段树的暴力。。。