首页 > 代码库 > [洛谷 P3398] 仓鼠找sugar
[洛谷 P3398] 仓鼠找sugar
题目描述
小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？
小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！
输入输出格式
输入格式：
第一行两个正整数n和q，表示这棵树节点的个数和询问的个数。
接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。
接下来q行，每行四个正整数a、b、c和d，表示节点编号，也就是一次询问，其意义如上。
输出格式：
对于每个询问，如果有公共点，输出大写字母“Y”；否则输出“N”。
输入输出样例
输入样例#1：
5 5 2 5 4 2 1 3 1 4 5 1 5 1 2 2 1 4 4 1 3 4 3 1 1 5 3 5 1 4
输出样例#1：
Y N Y Y Y
说明
本题时限1s，内存限制128M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。
20%的数据 n<=200,q<=200
40%的数据 n<=2000,q<=2000
70%的数据 n<=50000,q<=50000
100%的数据 n<=100000,q<=100000
话说这题老早就A了，当时是用LCA来A下来的。那不妨就说一下LCA的思路吧，过程就略了，dalao们肯定都会。题目意思就是在树上给出两条路径，判断是否有交点。
那么假设a,b的LCA是fx，c,d的LCA是fy。如果dep[fx]<dep[fy],说明如果有交点的话，fx必定是fy的祖先。那么此时，c，d中必有一个，LCA（c|d，fx）=fx。如果这样，那么就是有交点了。反之，dep[fy]>dep[fx]，那么就要考虑fy，a，b的关系。那么查找树上两点的最近公共祖先，用倍增算法查找是完全可以的。
1 //sugar 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=100005,maxe=100005,maxl=19; 7 int n,Q; 8 int son[maxe*2],nxt[maxe*2],lnk[maxn],tot; 9 int pa[maxn][maxl],dep[maxn]; 10 bool vis[maxn]; 11 inline int read(){ 12 int x=0; char ch=getchar(); 13 while (ch<‘0‘||ch>‘9‘) ch=getchar(); 14 while (ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); 15 return x; 16 } 17 void add(int x,int y){ 18 son[++tot]=y; nxt[tot]=lnk[x]; lnk[x]=tot; 19 } 20 void DFS(int d,int x,int p){ 21 dep[x]=d; vis[x]=1; pa[x][0]=p; 22 for (int j=lnk[x]; j; j=nxt[j]) if (!vis[son[j]]) DFS(d+1,son[j],x); 23 } 24 void RMQ(){ 25 for (int j=1; j<=18; j++) 26 for (int i=1; i<=n; i++) pa[i][j]=pa[pa[i][j-1]][j-1]; 27 } 28 int LCA(int x,int y){ 29 if (dep[x]<dep[y]) swap(x,y); 30 int dif=dep[x]-dep[y],ans=y; 31 for (int c=18; c>=0; c--) if (dif&(1<<c)) x=pa[x][c]; 32 if (x==y) return ans; 33 for (int c=18; c>=0; c--) if (pa[x][c]!=pa[y][c]) x=pa[x][c],y=pa[y][c]; 34 ans=pa[x][0]; 35 return ans; 36 } 37 bool go(int x,int y,int aim){ 38 int dif; 39 dif=dep[x]-dep[aim]; 40 if (dif>=0){ 41 for (int c=18; c>=0; c--) if (dif&(1<<c)) x=pa[x][c]; 42 if (x==aim) return 1; 43 } 44 dif=dep[y]-dep[aim]; 45 if (dif>=0){ 46 for (int c=18; c>=0; c--) if (dif&(1<<c)) y=pa[y][c]; 47 if (y==aim) return 1; 48 } 49 return 0; 50 } 51 int main(){ 52 n=read(),Q=read(); 53 for (int i=1; i<n; i++){ 54 int x=read(),y=read(); add(x,y),add(y,x); 55 } 56 DFS(1,1,1); 57 RMQ(); 58 for (; Q; Q--){ 59 int a=read(),b=read(),c=read(),d=read(); 60 int rx=LCA(a,b),ry=LCA(c,d); 61 bool f1=go(a,b,ry),f2=go(c,d,rx),f3=go(rx,rx,ry),f4=go(ry,ry,rx); 62 if ((f1&&f4)||(f2&&f3)) printf("%c\n",‘Y‘); else printf("%c\n",‘N‘); 63 } 64 return 0; 65 }
学了树链剖分后，用于解这题是再好不过的了。核心思想没有变，还是一样。但是，求最近公共祖先的方法变了一下。这里也就不解释了，仅提供思路，有兴趣的可以自行参考相关资料（树链剖分还是不错滴~~~）
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define Me(Arr) memset(Arr,0,sizeof Arr); 6 using namespace std; 7 const int maxn=100005,maxe=200005; 8 int n,Q; 9 int lnk[maxn],nxt[maxe],son[maxe],tot; 10 int size[maxn],fa[maxn],dep[maxn],gonxt[maxn],id[maxn],top[maxn],bottom[maxn],cloc; 11 int bel[maxn],cnt; 12 bool vis[maxn]; 13 int read(){ 14 int x=0; char ch=getchar(); 15 while (ch<‘0‘||ch>‘9‘) ch=getchar(); 16 while (ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); 17 return x; 18 } 19 void INIT(){ 20 tot=cloc=cnt=0; 21 Me(lnk); Me(nxt); Me(son); Me(size); 22 Me(fa); Me(dep); Me(gonxt); Me(id); Me(top); Me(bottom); Me(bel); 23 } 24 void add(int x,int y){ 25 nxt[++tot]=lnk[x],son[tot]=y,lnk[x]=tot; 26 } 27 void DFS_1(int x,int u,int layer){ 28 size[x]=1,fa[x]=u,dep[x]=layer; 29 for (int j=lnk[x]; j; j=nxt[j]) if (son[j]!=u){ 30 DFS_1(son[j],x,layer+1); size[x]+=size[son[j]]; 31 if (size[gonxt[x]]<size[son[j]]) gonxt[x]=son[j]; 32 } 33 } 34 void DFS_2(int x){ 35 id[x]=++cloc,bottom[x]=x; 36 if (gonxt[x]){top[gonxt[x]]=top[x],bel[gonxt[x]]=bel[x]; DFS_2(gonxt[x]); bottom[x]=bottom[gonxt[x]];} 37 for (int j=lnk[x]; j; j=nxt[j]) if (son[j]!=fa[x]&&son[j]!=gonxt[x]){ 38 top[son[j]]=son[j],bel[son[j]]=++cnt; 39 DFS_2(son[j]); 40 } 41 } 42 void prepare(){ 43 DFS_1(1,0,1); top[1]=bottom[1]=cnt=bel[1]=1; DFS_2(1); 44 } 45 int get(int x,int y){ 46 if (bel[x]==bel[y]) return dep[x]<dep[y]?x:y; 47 while (bel[x]!=bel[y]){ 48 if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]]; 49 } 50 return dep[x]<dep[y]?x:y; 51 } 52 int main(){ 53 n=read(),Q=read(),INIT(); 54 for (int i=1; i<n; i++){ 55 int x=read(),y=read(); add(x,y),add(y,x); 56 } 57 prepare(); 58 for (; Q; Q--){ 59 int a=read(),b=read(),c=read(),d=read(); 60 int fx=get(a,b),fy=get(c,d); 61 if (dep[fx]<dep[fy]) swap(a,c),swap(b,d),swap(fx,fy); 62 if (fx==get(fx,c)||fx==get(fx,d)) puts("Y"); else puts("N"); 63 } 64 return 0; 65 }
[洛谷 P3398] 仓鼠找sugar
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。