https://www.luogu.org/problemnew/show/P3398
题意简单概括一下就是求树上两条路径是否相交;
有这样一个性质:
if相交,则必有lca(a,b) 在路径c <-> d 上or lca(c,d) 在路径a <-> b 上;
接下来就是这样一个问题:
怎样判断一个点(x)是否在一条路径(a,b)上
如果满足以下两个条件,则在:
1.dep[x] >= lca(a,b);
2.lca(x,a) == x || lca(x,b) == x
#include <bits/stdc++.h> #define read read() #define up(i,l,r) for(register int i = (l);i <= (r);++i) #define down(i,l,r) for(register int i = (l);i >= (r);i--) #define traversal_vedge(i) for(register int i = head[u]; i ;i = e[i].nxt) #define ll long long using namespace std; int read { int x = 0, f = 1; char ch = getchar(); while(ch < 48 || ch > 57) {if(ch == '-')f = -1; ch = getchar();} while(ch >=48 && ch <=57) {x = 10 * x + ch - 48;ch = getchar();} return x * f; } //----------------------------------------------------------------- const int N = 100005; int n,q; struct edge{ int v,nxt; }e[N<<1];int tot,head[N]; void buildtree(int u,int v) {e[++tot] = (edge){v,head[u]}; head[u] = tot;} //----------------------------------------------------------------- int dep[N],size[N],top[N],fa[N]; void initdfs(int u){ dep[u] = dep[fa[u]] + 1; size[u] = 1; top[u] = u; int hson_id = 0,hson_size = 0; traversal_vedge(i) { int v = e[i].v; if(fa[u] == v) continue; fa[v] = u; initdfs(v); size[u] += size[v]; if(size[v] > hson_size) hson_id = v,hson_size = size[v]; } if(hson_id) top[hson_id] = u; } int find(int u){if(top[u] == u) return u;top[u] = find(top[u]); return top[u];} int lca(int x,int y){ if(find(x) != find(y)){ if(dep[top[x]] > dep[top[y]]) return lca(fa[top[x]],y); else return lca(x,fa[top[y]]); } return dep[x] > dep[y] ? y : x; } //----------------------------------------------------------------- bool ok; void query(int x,int a,int b){ if(lca(a,x) == x || lca(b,x) == x) ok = 1; } void work(){ initdfs(1); while(q--) { ok = 0; int a = read,b = read,c = read,d = read; int x = lca(a,b);int y = lca(c,d);//debug y = lca(a,b) if(dep[x] >= dep[y]) query(x,c,d); if(!ok) if(dep[y] >= dep[x]) query(y,a,b); if(ok == 1) printf("Y\n"); else printf("N\n"); } } void readdata(){ n = read; q = read; up(i,1,n-1) { int u = read,v = read; buildtree(u,v); buildtree(v,u); } } int main() { readdata(); work(); return 0; }