蒟蒻爆零求助QAQ
查看原帖
蒟蒻爆零求助QAQ
179561
cinis楼主2021/2/1 17:08
#include<bits/stdc++.h>
#define LL long long
#define U unsigned
#define INF 0x7fffffffffffffff
#define MINF -0x8000000000000000
bool isp(int x){
	if(x<2)return 0;
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0) return 0;
	}
	return 1;
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int gcd(int x,int y){
	return !y?x:gcd(y,x%y);
}
using namespace std;
/*int N,M,S,T,l,r=0x7f7f7f7f,m,h[600000],n[600000],w[600000],dt[600000],en,dis[600000];
struct node{
	int id,dis;
	bool operator < (const node &B) const{return dis>B.dis;}
};
void dij(){
	priority_queue<node>q;
	bool vis[600000]={};
	memset(dis,0x7f7f7f7f,sizeof dis);
	dis[S]=0;
	q.push((node){S,0});
	while(q.size()){
		int x=q.top().id;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int j=h[x];j;j=n[j]){
			int y=dt[j],ww=w[j];
			if(dis[y]<=dis[x]+ww)continue;
			dis[y]=dis[x]+ww;
			q.push((node){y,dis[y]});
		}
	}
    return ;
}
void add(int x,int y,int z){
	dt[++en]=y,n[en]=h[x],w[en]=z,h[x]=en;
	return ;
}*/
struct edge{
	int dt,n;
}e[3000000];
struct node{
	int id,dep;
	bool operator <(const node &oth) const{
		return dep<oth.dep;
	}
}seq[3000000],fn[1200000][30];
int n=read(),m=read(),len,rt,hd[3000000],dep[3000000],id[3000000],cnt;
void add(int a,int b){
	cnt++;
	e[cnt].n=hd[a];
	hd[a]=cnt;
	e[cnt].dt=b;
}
void dfs(int cur,int fa){
	dep[cur]=dep[fa]+1;
	seq[++len]=node{cur,dep[cur]};
	id[cur]=len;
	for(int i=hd[cur];i;i=e[i].n){
		if(e[i].dt!=fa){
			dfs(e[i].dt,cur);
			seq[++len]=node{cur,dep[cur]};
		}
	}
	return ;
}
int LCA(int l,int r){
	if(l>r)swap(l,r);
	int lg2=log2(r-l+1);
//	cout<<lg2<<"    lg2\n\n\n\n\n";
	return min(fn[l][lg2],fn[r-(1<<lg2)+1][lg2]).id;
}
int range(int a,int b){	
//		puts("nmsl");
//	cout<<LCA(a,b)<<"   LCA a,b\n\n\n\n";
	return abs(dep[a]-dep[LCA(a,b)])+abs(dep[b]-dep[LCA(a,b)]);
}
int main(){
	for(int i=1,a,b;i<n;i++){
		a=read(),b=read();
		add(a,b),add(b,a);
	} 
	dfs(1,0);
	for(int i=1;i<=len;i++){
		fn[i][0]=seq[i];
	}
	for(int j=1;j<=log2(len);j++)
		for(int i=1;i<=len;i++)
			fn[i][j]=min(fn[i][j-1],fn[i+(1<<(j-1))][j-1]);
	for(int i=1;i<=m;i++){
		int a=read(),b=read(),c=read(),d=read();
		if( range(a,LCA(c,d))+range(b,LCA(c,d))==range(a,b)||
			range(c,LCA(a,b))+range(d,LCA(a,b))==range(c,d))puts("Y");
		else puts("N");
	}
    return 0;
}

样例最后一个点炸掉qaq

2021/2/1 17:08
加载中...