听了教练的考前须知 蒟蒻紧张的要死 只想做信心题
同时满足：c或者d在x子树里 a或者b在y子树里 其中x=lca(a,b),y=lca(c,d)
#include<bits/stdc++.h> #define N 100005 using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); } struct Edge { int to,next; }edge[2*N]; int n,Q,first[N],tot; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } int depth[N],father[N],size[N],maxson[N]; void dfs1(int now,int fa) { father[now]=fa; depth[now]=depth[fa]+1; size[now]=1; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs1(vis,now); size[now]+=size[vis]; if(size[maxson[now]]<size[vis]) maxson[now]=vis; } } int top[N],dfn[N],sign; void dfs2(int now,int topf) { top[now]=topf; dfn[now]=++sign; if(maxson[now]) dfs2(maxson[now],topf); for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==father[now]||vis==maxson[now]) continue; dfs2(vis,vis); } } inline int lca(int x,int y) { while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); x=father[top[x]]; } if(depth[x]<depth[y]) swap(x,y); return y; } int main() { read(n),read(Q); for(int i=1,x,y;i<n;i++) { read(x),read(y); addedge(x,y); addedge(y,x); } dfs1(1,0); dfs2(1,1); while(Q--) { int flag=0; int a,b,c,d,x,y; read(a),read(b),read(c),read(d); x=lca(a,b); y=lca(c,d); if((dfn[x]<=dfn[c]&&dfn[c]<=dfn[x]+size[x]-1)||(dfn[x]<=dfn[d]&&dfn[d]<=dfn[x]+size[x]-1)) flag++; //如果c或者d在x子树里 if((dfn[y]<=dfn[a]&&dfn[a]<=dfn[y]+size[y]-1)||(dfn[y]<=dfn[b]&&dfn[b]<=dfn[y]+size[y]-1)) flag++;//如果a或者b在y子树里 (flag==2)?puts("Y"):puts("N"); } }转载于:https://www.cnblogs.com/Patrickpwq/articles/9915200.html
相关资源：各显卡算力对照表！