竞赛课想找一道水一点的tarjan题，看看这么久没做题手感有没有掉...

结果这题貌似不是tarjan啊...应该是LCA...假的标签！！

一遍过样例+一遍AC祭（好吧这么水的题也没啥好开心的）

 

大概就是给一棵树，和两条路径，判断两条路径有无公共顶点。

 

随便画一棵树，然后会发现，两条路径有公共部分的话，必定有一条路径（的两个端点）的LCA在另一条路径上

这样我们只要判断一个节点是否在一条路径上即可

然后联想到绝对值的几何意义（反正我是这么想到的...）满足以下规律的才有可能满足节点lca在路径a-b上

$$dis(lca,a)+dis(lca,b)==dis(a,b)$$

 

 注意:要判断两次，因为有可能是LCA(a,b)在c-d上，也有可能是LCA(c,d)在a-b上

然后我打的树剖LCA，看着不爽的可以换成自己LCA啦

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define writeln(x)  write(x),puts("")
 5 #define writep(x)   write(x),putchar(' ')
 6 using namespace std;
 7 inline int read(){
 8     int ans=0,f=1;char chr=getchar();
 9     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
11     return ans*f;
12 }void write(int x){
13     if(x<0) putchar('-'),x=-x;
14     if(x>9) write(x/10);
15     putchar(x%10+'0');
16 }const int M = 1e5+5;
17 int head[M],ver[M<<1],nxt[M<<1],tot,n,m,idx[M],fa[M],son[M],sz[M],tp[M],dep[M];
18 inline void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
19 void dfs1(int x,int f){
20     fa[x]=f,dep[x]=dep[f]+1;sz[x]=1;
21     for(int i=head[x];i;i=nxt[i]){
22         if(ver[i]==f) continue;
23         dfs1(ver[i],x);
24         sz[x]+=sz[ver[i]];
25         if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
26     }
27 }int t;
28 void dfs2(int x,int topf){
29     tp[x]=topf,idx[x]=++t;
30     if(!son[x]) return;
31     dfs2(son[x],topf);
32     for(int i=head[x];i;i=nxt[i])
33         if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
34 }
35 int LCA(int x,int y){
36     while(tp[x]!=tp[y]){
37         if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
38         x=fa[tp[x]];
39     }if(dep[x]>dep[y]) swap(x,y);
40     return x;
41 }
42 int DIS(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];}
43 inline bool check(int a,int b,int c,int d){
44     int x=LCA(a,b);
45     if(DIS(x,c)+DIS(x,d)==DIS(c,d)) return 1;
46     return 0;
47 }
48 int main(){
49     n=read(),m=read();
50     for(int i=1,x,y;i<n;i++){
51         x=read(),y=read();
52         add(x,y),add(y,x);
53     }dfs1(1,0),dfs2(1,1);
54     while(m--){
55         int a=read(),b=read(),c=read(),d=read();
56         if(check(a,b,c,d)||check(c,d,a,b)) puts("Y");
57         else puts("N");
58     }
59     return 0;
60 }