Chip 'n' Dale rescue rangers! But observant viewers know that help is usually required by Chip and Dale themselves. Today you are in the role of cunning Gadget Hackwrench.
So, Chip and Dale are again in the paws of Fat Cat. He doesn't like rodents much and therefore prepared a treacherous test. He is going to put them to a labyrinth and see if they can escape from it. The labyrinth is actually built as a tree where each edge has fixed direction (by definitiontree is a connected unoriented graph without cycles).
Gadget has intercepted a talk between Fat Cat and his henchmen about future tests. For each test round she knows the exact location where Chip and Dale are to be put by Fat Cat and the location of an exit. Gadget wants to compute whether they will be able to find an exit for each test.
The first line of input contains an integer N (1 ≤ N ≤ 105) — the number of vertices in a graph.
On the next N - 1 lines of input directed arcs of the tree are given. On the (i + 1)th line integer numbers ai and bi are given (1 ≤ ai, bi ≤ N) denoting an arc from vertex ai to vertex bi. It is guaranteed that arcs a1, a2, ..., an - 1 without orientation form a tree.
Then a string with integer number M (1 ≤ M ≤ 105) is given — the number of queries to process. Next M lines describe queries: (n + 1 + i)thline contain integers xi and yi (1 ≤ xi, yi ≤ N).
For each query please output a separate line containing 'Yes' (without quotes) if graph contains a path between xi and yi, or 'No' (without quotes) in other case.
4 1 2 3 1 4 1 6 1 2 3 2 2 3 4 2 4 3 2 1
Yes Yes No Yes No No
由于3 2能够通行而2 3无法通行可知通行有方向上的限制，为了解决这种问题，可以人为地在每一对（u，v）之间加上一个负边，长度为-1，而设原来方向的边为+1，
那么对于每个lca来说，如果u到lca的距离由wei负边构成，v到lca的距离由正边构成，那么这两个点联通
#include <iostream> #include <cstdio> #include <cstring> #define scan(x) scanf("%d",&x) #define scan2(x,y) scanf("%d%d",&x,&y) #define scan3(x,y,z) scanf("%d%d%d",&x,&y,&z) using namespace std; const int Max=1e5+10; const int E=2e5+10; int head[Max],nex[E],pnt[E],cost[E],edge; int vex[Max<<1],R[Max<<1],vis[Max],dis[Max],first[Max],tot; int n; void Addedge(int u,int v,int c) { pnt[edge]=v; cost[edge]=c; nex[edge]=head[u]; head[u]=edge++; } void dfs(int u,int deep) { vis[u]=1; vex[++tot]=u; first[u]=tot; R[tot]=deep; for(int x=head[u]; x!=-1; x=nex[x]) { int v=pnt[x],c=cost[x]; if(!vis[v]) { dis[v]=dis[u]+c; dfs(v,deep+1); vex[++tot]=u; R[tot]=deep; } } } int dp[Max<<1][25]; void ST(int n) { int x,y; for(int i=1; i<=n; i++) dp[i][0]=i; for(int j=1; (1<<j)<=n; j++) { for(int i=1; i+(1<<j)-1<=n; i++) { x=dp[i][j-1]; y=dp[i+(1<<(j-1))][j-1]; dp[i][j]=(R[x]<R[y]?x:y); } } } int RMQ(int l,int r) { int k=0,x,y; while((1<<(k+1))<=r-l+1) k++; x=dp[l][k]; y=dp[r-(1<<k)+1][k]; return (R[x]<R[y])?x:y; } int LCA(int u,int v) { int x=first[u],y=first[v]; if(x>y) swap(x,y); int res=RMQ(x,y); return vex[res]; } int vis2[Max]; void Init() { edge=0; memset(head,-1,sizeof(head)); memset(nex,-1,sizeof(nex)); memset(vis,0,sizeof(vis)); memset(vis2,0,sizeof(vis2)); } int main() { int T,Q; Init(); int u,v,c; scan(n); for(int i=0; i<n-1; i++) { scan2(u,v); Addedge(u,v,1); Addedge(v,u,-1); vis2[v]=1; } int root=1; for(int i=1; i<=n; i++) if(!vis2[i]) { root=i; break; } tot=0; dis[root]=0; dfs(root,1); ST(2*n); scan(Q); while(Q--) { scan2(u,v); int lca=LCA(u,v); cout<<lca<<endl; int depu=R[first[u]]-R[first[lca]]; int depv=R[first[v]]-R[first[lca]]; int disu=dis[u]-dis[lca]; int disv=dis[v]-dis[lca]; //lca与u之间都要为负边，lca与v之间都要为正边 //u到lca距离全负,因为u的父亲由负边而来 //v到lca距离全正 if(depu==-disu&&depv==disv) puts("Yes"); else puts("No"); } return 0; }