题意：给一棵含n个结点的树，现要查询从a到b的路径中是否包含c，共q次查询。1=<n，q<=100000
分析：由于在树中从一个结点走到另一个结点的路径是唯一的，其实说的这条路径就是最短路径，然后问题转化为判断一个点是否为在一条最短路径上，此时就不难想到这个这个判断条件d(a,c)+d(c,b)=d(a,b)，问题就转化为查询树中2个结点之间的距离，这个可以用LCA来做（参考上一篇），考虑到n和q都比较大，所以用离线LCA.
View Code
#include <stdio.h> #include <string.h> #define N 100010 #define M 200010 int n,q,e,eq; int p[N],d[N]; int first[N],next[M],v[M]; int first_q[N],next_q[3*M],u_q[3*M],v_q[3*M],lca[3*M]; bool ok[3*M]; void make_set(int i) { p[i]=i; } int find_set(int i) { if(i^p[i]) p[i]=find_set(p[i]); return p[i]; } void union_set(int i,int j) { i=find_set(i),j=find_set(j); p[j]=i; } void init() { e=eq=0; memset(first,-1,sizeof(first)); memset(first_q,-1,sizeof(first_q)); memset(p,-1,sizeof(p)); memset(ok,0,sizeof(ok)); memset(lca,0,sizeof(lca)); } void add(int a,int b) { v[e]=b; next[e]=first[a]; first[a]=e++; } void add_q(int a,int b) { u_q[eq]=a; v_q[eq]=b; next_q[eq]=first_q[a]; first_q[a]=eq++; } void get_d(int a,int fa) { int i,b; d[a]=d[fa]+1; for(i=first[a];i!=-1;i=next[i]) { b=v[i]; if(b!=fa) get_d(b,a); } } void dfs(int a) { int i,b; make_set(a); for(i=first[a];i!=-1;i=next[i]) { b=v[i]; if(p[b]==-1) { dfs(b); union_set(a,b); } } for(i=first_q[a];i!=-1;i=next_q[i]) if(!ok[i]) { b=v_q[i]; if(p[b]!=-1) lca[i]=find_set(b),ok[i]=true; } } int main() { int a,b,c; while(~scanf("%d%d",&n,&q)) { init(); for(int i=0;i<n-1;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } while(q--) { scanf("%d%d%d",&a,&b,&c); add_q(a,b); add_q(a,c); add_q(b,c); add_q(b,a); add_q(c,a); add_q(c,b); } d[0]=-1; get_d(1,0); dfs(1); int dist[3]; for(int i=0;i<eq;i+=6) { for(int j=0;j<3;j++) { a=u_q[i+j]; b=v_q[i+j]; c=lca[i+j]; if(c==0) c=lca[i+j+3]; dist[j]=d[a]+d[b]-2*d[c]; } if(dist[0]==dist[1]+dist[2]) puts("YES"); else puts("NO"); } puts(""); } return 0; }