Luogu P3398 仓鼠找sugar 倍增LCA 树

题目描述
题目
差不多是裸的LCA吧
只要处理好两条相交路径之间的关系就好了
如果两条路径相交，那么一条路径的LCA一定在另一条路径上
那么需要满足

dep[lca1] >= dep[lca2] lca(lca1,s) == lca1 || lca(lca1,t) == lca1

【Luogu P3398 仓鼠找sugar 倍增LCA】代码

#include #include #include #include #include using namespace std; const int N=100010; int n,q,now,head[N],f[N][20],dep[N]; struct E{int to,next; }e[N<<1]; void build(int u,int v){e[++now].to=v; e[now].next=head[u]; head[u]=now; }void dfs1(int u,int fa) { f[u][0]=fa; for(int i=1; f[u][i-1]; i++) f[u][i]=f[f[u][i-1]][i-1]; for(int i=head[u]; i; i=e[i].next) { int v=e[i].to; if(v == fa) continue; dep[v]=dep[u]+1; dfs1(v,u); } }int lca(int u,int v) { if(dep[u] > dep[v]) swap(u,v); int d=dep[v]-dep[u]; for(int i=0; (1<= 0; i--) if(f[u][i] != f[v][i]) u=f[u][i],v=f[v][i]; return f[u][0]; }int read(){ int out=0; char c=getchar(); while(c > '9' || c < '0') c=getchar(); while(c >= '0' && c <= '9') {out=(out<<1)+(out<<3)+c-'0'; c=getchar(); }return out; }void init() { n=read(),q=read(); for(int i=1; i dep[u1] && dep[lca2] >dep[v1]) {printf("N\n"); continue; } if(dep[lca1] > dep[u2] && dep[lca1] >dep[v2]) {printf("N\n"); continue; } if(dep[lca1] >= dep[lca2]) { if(lca1 == lca(lca1,u2)) {printf("Y\n"); continue; } if(lca1 == lca(lca1,v2)) {printf("Y\n"); continue; } printf("N\n"); continue; } if(dep[lca2] >= dep[lca1]) { if(lca2 == lca(lca2,u1)) {printf("Y\n"); continue; } if(lca2 == lca(lca2,v1)) {printf("Y\n"); continue; } printf("N\n"); continue; } printf("N\n"); } }int main() { init(); solve(); return 0; }