luoguP398 仓鼠找sugar

本文主要是介绍luoguP398 仓鼠找sugar，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

luoguP398 仓鼠找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

数据规模
20%的数据 n<=200,q<=200
40%的数据 n<=2000,q<=2000
70%的数据 n<=50000,q<=50000
100%的数据 n<=100000,q<=100000

接下来讲一下如何用LCA解决这道题，我们知道如果两个松鼠遇上的话，也就是说这两者的路劲就会至少有一个重合点，而LCA在表层看来只能解决他们的最近公共点，那么如何转化呢。
根的问题就不用说了，(随便挑几个点就好了)，我默认为1。好我们现在可以大概分析一下了。

大的情况可以分为两个
1.不相交，2.相交

不想交的情况也就意味着他们不在一棵子树上，也就是说，设a至b为一条路线，c至d也是一条路线，那么lca(a,b)和lca(c,d)的lca实际上不等于前两者，可能说到这里你们或许还很困惑，(手动模拟一下不就好了)。

先放一个前置知识：当lca中的两个值有一个值为此lca答案的话，那么这两个点就在同一条链上。
简单来说就是lca(a,b)=a或b。

那么如果lca(a,b)和lca(c,d)的lca等于前两者之一的话就符合有相交点了吗？很显然不是。
1
2 3
4 5 6 假设这是一棵树，额，有点简陋但没关系。
从4到5，和从6到1很显然满足我所说的上列条件，那么这个时候就要分情况判断了。

         int t1=lca(x,y),t2=lca(z,e),t3=lca(t1,t2);if(t1==t3&&(lca(t2,x)==t2||lca(t2,y)==t2)) printf("Y\n");else if(t2==t3&&(lca(t1,z)==t1||lca(t1,e)==t1)) printf("Y\n");

只有上述情况才是成立的，因为，当t1==t3时，显然，以x和y构成的一条路径是这棵子树的“主宰”。那么如果他们两条路径联通的话，z，e的公共点肯定与x或y在同一条直线上。
相反亦如此。
如果两种情况都不是，那就不行了。

#代码

#include<iostream>
#include<cstdio>
#include<cmath> 
#define re register 
#define ll long long
const int N=100001,M=31;
using namespace std;
int n,q,m[N];
int x,y,z,e;
int st[N][M],con[N],dep[N],dd;
int cnt,ne[2*N],h[2*N],to[2*N];	
void add(int u,int v)
{cnt++;ne[cnt]=h[u];h[u]=cnt;to[cnt]=v;
}
void dfs(int x,int fa)
{st[x][0]=fa; dep[x]=dep[fa]+1;for(int i=h[x];i;i=ne[i]){if(to[i]==fa) continue;dfs(to[i],x);con[x]+=con[to[i]];}con[x]++;
}
int lca(int x,int y)
{if(dep[x]>dep[y]) swap(x,y);int d=dep[y]-dep[x],step=0;while(d){if(d&1) y=st[y][step];step++,d>>=1;}if(x==y) return x;int k=25;while(k>=0){if(st[x][k]!=st[y][k]) x=st[x][k],y=st[y][k];k--;}return st[x][0];
}
inline int qread(){int x=0,f=0;char c=getchar();while(c>'9'||c<'0') f=c=='-',c=getchar();while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return f?-x:x;
}
int main()
{n=qread(),q=qread();for(int i=1;i<=n-1;i++){x=qread(),y=qread();add(x,y),add(y,x);} dfs(1,0);for(re int j=1;j<=25;j++)for(re int i=1;i<=n;i++)st[i][j]=st[st[i][j-1]][j-1];	for(re int i=1;i<=q;i++){x=qread(),y=qread(),z=qread(),e=qread();int t1=lca(x,y),t2=lca(z,e),t3=lca(t1,t2);if(t1==t3&&(lca(t2,x)==t2||lca(t2,y)==t2)) printf("Y\n");else if(t2==t3&&(lca(t1,z)==t1||lca(t1,e)==t1)) printf("Y\n");else printf("N\n");}return 0;	
} 

这篇关于luoguP398 仓鼠找sugar的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---