题目描述

每年的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

输入
1
7 2
1 2
2 3
3 4
4 7
1 5
1 6
3 5 6
7 5 6

输出
YES
NO

思路：
a:何老师，b:sk同学，c:小c同学
如果 dis(a,1) < dis(b,c) + dis(c,1) 这样肯定可以输出yes即可
如果 dis(a,1) == dis(b,c) + dis(c,1)这个时候需要判断一下a,c是否lca是根节点的一个儿子，如果是，则a老师显然只需要花费dis(a,lca(a,c))的时间，并不需要再往上面走了，就是它可以在lca等同学，这个时候输出YES，如果lca(a,c) = 1则老师始终慢同学一步，输出no即可
如果dis(a,1) > dis(b,c) + dis(c,1)输出no
这是第一次写lca也是第一次学lca，感觉lca可以处理树上的两个节点最短距离。
代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int maxn = 1e6 + 100;
struct edge{
    int v,next;
    edge(){}
    edge(int a,int b):v(a),next(b){}
}e[maxn << 1];
int head[maxn],tot;
int dep[maxn],f[maxn][25];
void add(int u,int v){
    e[++tot].v = v;
    e[tot].next = head[u];
    head[u] = tot;
}
void dfs(int v,int fa){
    dep[v] = dep[fa] + 1;
    for(int i = 1; (1 << i) <= dep[v] ;i ++){
        f[v][i] = f[f[v][i - 1]][i - 1];
    }
    for(int i = head[v];i;i = e[i].next){
        if(e[i].v != fa){
            f[e[i].v][0] = v;
            dfs(e[i].v,v);
        }
    }
}
int lca(int x,int y){
    if(dep[x] < dep[y])swap(x,y);
    for(int i = 20; i >= 0; i--){
        if(dep[f[x][i]] >= dep[y]) x = f[x][i];
        if(x == y)return x;
    }
    for(int i = 20; i >= 0; i--){
        if(f[x][i] != f[y][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
void solved(){
    int t;scanf("%d",&t);
    while(t--){
        memset(head,0,sizeof(head));
        memset(dep,0,sizeof(dep));
        memset(f,0,sizeof(f));
        int n,q;scanf("%d%d",&n,&q);
        for(int i = 1; i < n; i++){
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        dfs(1,0);
        while(q--){
            int a,b,c;scanf("%d%d%d",&a,&b,&c);
            int la = dep[a] - dep[1];
            int LCA = lca(b,c);
            int b_c = dep[b] - dep[LCA] + dep[c] - dep[LCA];
            int ld = b_c + dep[c] - dep[1]; 
            if(la < ld)printf("YES\n");
            else if(la == ld){
                if(lca(a,c) == 1){//不在同一棵子树上，老师总是慢学生一步
                    printf("NO\n");
                }else printf("YES\n");//在同一子树上，虽然距离相同，但是但是可以先到lca等同学就行了
            }else printf("NO\n");
        }
    }
}
int main(){
    solved();
    return 0;
}