牛客算法周周练1

链接：https://ac.nowcoder.com/acm/contest/5086/C
来源：牛客网

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

每年的BNU校赛都会有两次赛前培训，为此就需要去借教室，由于SK同学忙于出题，这个事情就由小Q同学来跑腿。SK同学准备从宿舍出发，把借教室的单子交给小Q同学让他拿去教务处盖章，但是何老师突然发现SK同学好像借错教室了，想抢在借教室的单子被送到教务处之前拦截下来。

现在把校园抽象成一棵n个节点的树，每条边的长度都是一个单位长度，从1到n编号，其中教务处位于1号节点，接下来有q个询问，每次询问中SK同学会从B号节点出发，到C号节点找到小Q同学并将借教室的单子交给他，然后小Q同学再从C号节点出发前往教务处，何老师会从A号节点出发开始拦截。

所有人在一个单位时间内最多走一个单位距离，只要何老师在单子还没被送到教务处之前遇到拿着单子的同学都算拦截成功，如果小Q同学已经到了教务处，那么由于小Q同学手速极快，单子会被立即交上去，即使何老师到了教务处也无济于事，你需要判断何老师是否能够拦截成功。

输入描述:

第一行是一个正整数T(≤ 5)，表示测试数据的组数，对于每组测试数据，第一行是两个整数n,q(1≤ n,q ≤ 100000)，分别表示节点数和询问数，接下来n-1行，每行包含两个整数x,y(1≤ x,y ≤ n)，表示x和y之间有一条边相连，保证这些边能构成一棵树，接下来q行，每行包含三个整数A,B,C(1 ≤ A,B,C ≤ n)，表示一个询问，其中A是何老师所在位置，B是SK同学所在位置，C是小Q同学所在位置，保证小Q同学初始不在教务处。

输出描述:

对于每个询问，输出一行，如果何老师能成功拦截则输出"YES"（不含引号），否则输出"NO"（不含引号）。

示例1

输入

输出

YES
NO

关于LCA：https://www.cnblogs.com/jiamian/p/12749397.html

DFS求出以1为根的全部节点的深度，并且预处理出全部的fa数组。

从结点A到结点1花费的时间(走的路程) dis1=deep[A]

从节点B到结点C再到结点1花费的时间(走的路程) dis2=deep[B]+2*(deep[C]-deep[LCA(B,C)]) (不理解的画图看看)

如果dis1<dis2，一定可以拦截成功。

如果dis1==dis2，需要判断LCA(A, C)是否等于1，如果等于1说明同时到达结点1，拦截失败，如果不是1说明可以提前拦截下来。

如果dis1>dis2，一定拦截失败。

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 #define pb push_back
 4 const int INF = 0x3f3f3f3f;
 5 const double eps = 1e-8;
 6 const int mod = 1e9+7;
 7 const int maxn = 1e5+10;
 8 using namespace std;
 9 
10 struct edge
11 {
12     int to;
13     int next;
14 }E[maxn<<1];//注意边的条数
15 int head[maxn], tot;
16 void add(int u,int v)
17 {
18     E[tot].to=v;
19     E[tot].next=head[u];
20     head[u]=tot++;
21 }
22 
23 int deep[maxn];
24 int fa[maxn][25];
25 void getdeep(int u, int pre)
26 {
27     deep[u] = deep[pre]+1;
28     fa[u][0] = pre;
29     for(int i=1;(1<<i)<=deep[u];i++)
30         fa[u][i] = fa[fa[u][i-1]][i-1];
31     for(int i=head[u];i!=-1;i=E[i].next)
32     {
33         if(E[i].to==pre) continue;
34         getdeep(E[i].to, u);
35     }
36 }
37 int LCA(int x, int y)
38 {
39     if (deep[x]<deep[y]) swap(x,y);
40     int dx = deep[x], dy = deep[y], xx = x, yy = y;
41     for (int cha=dx-dy,i=0; cha; cha>>=1,i++)
42         if(cha&1) xx = fa[xx][i];
43     if (yy==xx) return yy;
44     for (int i=24;i>=0;i--)
45     {
46         if (fa[xx][i]==fa[yy][i]) continue;
47         xx = fa[xx][i]; yy = fa[yy][i];
48     }
49     return fa[xx][0];
50 }
51 void init()
52 {
53     tot=0;
54     memset(head,-1,sizeof(head));
55     memset(deep,0,sizeof(deep));
56     memset(fa,0,sizeof(fa));
57 }
58 
59 int main()
60 {
61     #ifdef DEBUG
62     freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
63     #endif
64     
65     int T;
66     scanf("%d",&T);
67     while(T--)
68     {
69         int n,q;
70         scanf("%d %d",&n,&q);
71         init();//别忘了
72         for(int i=1;i<n;i++)//建树
73         {
74             int u,v;
75             scanf("%d %d",&u, &v);
76             add(u,v); add(v,u);
77         }
78         getdeep(1, 0);//用0，别用-1
79           for(int i=1;i<=q;i++)//查询
80           {
81               int a,b,c;
82               scanf("%d %d %d",&a, &b, &c);
83               int P1 = LCA(a, c);
84               int P2 = LCA(b, c);
85               int dis1 = deep[a];
86               int dis2 = deep[b]+2*deep[c]-2*deep[P2];
87               if(dis1<dis2||(dis1==dis2&&P1!=1)) printf("YES
");
88               else printf("NO
");
89           }
90     } 
91     
92     return 0;
93 }