题目描述
小仓鼠的和他的基（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
My Solution
借用题解里沧澜的原话：
如果两条路径相交，那么一定有一条路径的LCA在另一条路径上
而判断一个节点x，是否在路径s-t上需要满足如下几个条件
- deep[x]>=deep[LCA(s,t)] - LCA(s,x)=x或LCA(t,x)=x;所以分两种情况讨论一下即可
剩下的就是lca模板了，找根我用了点分治里找重心
暂时只会倍增lca QwQ
再犯sb错误，把&打成了&&
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
#define q1 first
#define q2 second
#define ss first
#define tt second inline int read(){
char ch;
int re=;
bool flag=;
while((ch=getchar())!='-'&&(ch<''||ch>''));
ch=='-'?flag=:re=ch-'';
while((ch=getchar())>=''&&ch<='') re=re*+ch-'';
return flag?-re:re;
} struct edge{
int to,next;
edge(int to=,int next=):
to(to),next(next){};
};
const int maxn=;
const int maxm=maxn<<;
const int maxlogn=;
typedef pair<int,int> PII;
typedef pair<PII,PII> PP;
int n,q;
vector<PP> ques;
int cnt=;
int head[maxn];
edge edges[maxm];
int root;
int F[maxn],son[maxn];
bool vis[maxn];
int depth[maxn],parent[maxlogn][maxn];
int sum; inline void add_edge(int from,int to){
edges[++cnt]=edge(to,head[from]);
head[from]=cnt;
edges[++cnt]=edge(from,head[to]);
head[to]=cnt;
} inline void add_ques(int a,int b,int c,int d){
ques.push_back(make_pair(make_pair(a,b),make_pair(c,d)));
} void getroot(int x,int fa){
son[x]=; F[x]=;
for(int ee=head[x];ee;ee=edges[ee].next)
if(edges[ee].to!=fa&&!vis[edges[ee].to]){
getroot(edges[ee].to,x);
son[x]+=son[edges[ee].to];
F[x]=max(F[x],son[edges[ee].to]);
}
F[x]=max(F[x],sum-son[x]);
if(F[x]<F[root]) root=x;
} void dfs(int v,int fa,int deep){
parent[][v]=fa;
depth[v]=deep;
for(int ee=head[v];ee;ee=edges[ee].next)
if(edges[ee].to!=fa) dfs(edges[ee].to,v,deep+);
} void init(){
memset(head,,sizeof head);
n=read(),q=read();
for(int i=;i<n-;i++){
int from=read(),to=read();
add_edge(from,to);
}
for(int i=;i<q;i++){
int a=read(),b=read(),c=read(),d=read();
add_ques(a,b,c,d);
}
memset(vis,,sizeof vis);
sum=F[root=]=n;
getroot(,);
dfs(root,-,);
for(int k=;k+<maxlogn;k++)
for(int v=;v<=n;v++)
if(parent[k][v]<) parent[k+][v]=-;
else parent[k+][v]=parent[k][parent[k][v]];
} int lca(int u,int v){
if(depth[u]>depth[v]) swap(u,v);
for(int k=;k<maxlogn;k++)
if(depth[v]-depth[u]>>k&)
v=parent[k][v];
if(u==v) return u;
for(int k=maxlogn-;k>=;k--)
if(parent[k][u]!=parent[k][v]){
u=parent[k][u];
v=parent[k][v];
}
return parent[][u];
} bool check(PP qu){
int lca1=lca(qu.q1.ss,qu.q1.tt),lca2=lca(qu.q2.ss,qu.q2.tt);
if(depth[lca1]>=depth[lca2]&&(lca1==lca(qu.q2.ss,lca1)||lca1==lca(qu.q2.tt,lca1)))
return ;
if(depth[lca2]>=depth[lca1]&&(lca2==lca(qu.q1.ss,lca2)||lca2==lca(qu.q1.tt,lca2)))
return ;
return ;
} void solve(){
for(int i=;i<q;i++)
if(check(ques[i])) puts("Y");
else puts("N");
} int main(){
//freopen("temp.in","r",stdin);
init();
solve();
return ;
}
就算孤岛已没有四季 也没人提及你的美丽 我还是要飞去那里
