题目链接：bnu52509

Borrow Classroom

<label style="font-weight:bold;">Time Limit: </label>5000ms

<label style="font-weight:bold;">Memory Limit: </label>262144KB

64-bit integer IO format: %lld Java class name: Main

Prev Submit Status Statistics Discuss Next

Font Size: <button class="ui-button ui-widget ui-state-default ui-corner-all ui-button-icon-only" id="font-plus" style="font-family:'Trebuchet MS', Helvetica, Arial, sans-serif;font-size:1.1em;border-width:1px;border-style:solid;border-color:rgb(204,204,204);font-weight:bold;color:rgb(51,131,187);overflow:visible;" title="+"> + </button> <button class="ui-button ui-widget ui-state-default ui-corner-all ui-button-icon-only" id="font-minus" style="font-family:'Trebuchet MS', Helvetica, Arial, sans-serif;font-size:1.1em;border-width:1px;border-style:solid;border-color:rgb(204,204,204);font-weight:bold;color:rgb(51,131,187);overflow:visible;" title="-"> - </button>

Type: <select id="utags" name="utags"><option value="0"> None</option><option value="1"> Graph Theory</option><option value="2"> 2-SAT</option><option value="3"> Articulation/Bridge/Biconnected Component</option><option value="4"> Cycles/Topological Sorting/Strongly Connected Component</option><option value="5"> Shortest Path</option><option value="6"> Bellman Ford</option><option value="7"> Dijkstra/Floyd Warshall</option><option value="8"> Euler Trail/Circuit</option><option value="9"> Heavy-Light Decomposition</option><option value="10"> Minimum Spanning Tree</option><option value="11"> Stable Marriage Problem</option><option value="12"> Trees</option><option value="13"> Directed Minimum Spanning Tree</option><option value="14"> Flow/Matching</option><option value="15"> Graph Matching</option><option value="16"> Bipartite Matching</option><option value="17"> Hopcroft–Karp Bipartite Matching</option><option value="18"> Weighted Bipartite Matching/Hungarian Algorithm</option><option value="19"> Flow</option><option value="20"> Max Flow/Min Cut</option><option value="21"> Min Cost Max Flow</option><option value="22"> DFS-like</option><option value="23"> Backtracking with Pruning/Branch and Bound</option><option value="24"> Basic Recursion</option><option value="25"> IDA* Search</option><option value="26"> Parsing/Grammar</option><option value="27"> Breadth First Search/Depth First Search</option><option value="28"> Advanced Search Techniques</option><option value="29"> Binary Search/Bisection</option><option value="30"> Ternary Search</option><option value="31"> Geometry</option><option value="32"> Basic Geometry</option><option value="33"> Computational Geometry</option><option value="34"> Convex Hull</option><option value="35"> Pick's Theorem</option><option value="36"> Game Theory</option><option value="37"> Green Hackenbush/Colon Principle/Fusion Principle</option><option value="38"> Nim</option><option value="39"> Sprague-Grundy Number</option><option value="40"> Matrix</option><option value="41"> Gaussian Elimination</option><option value="42"> Matrix Exponentiation</option><option value="43"> Data Structures</option><option value="44"> Basic Data Structures</option><option value="45"> Binary Indexed Tree</option><option value="46"> Binary Search Tree</option><option value="47"> Hashing</option><option value="48"> Orthogonal Range Search</option><option value="49"> Range Minimum Query/Lowest Common Ancestor</option><option value="50"> Segment Tree/Interval Tree</option><option value="51"> Trie Tree</option><option value="52"> Sorting</option><option value="53"> Disjoint Set</option><option value="54"> String</option><option value="55"> Aho Corasick</option><option value="56"> Knuth-Morris-Pratt</option><option value="57"> Suffix Array/Suffix Tree</option><option value="58"> Math</option><option value="59"> Basic Math</option><option value="60"> Big Integer Arithmetic</option><option value="61"> Number Theory</option><option value="62"> Chinese Remainder Theorem</option><option value="63"> Extended Euclid</option><option value="64"> Inclusion/Exclusion</option><option value="65"> Modular Arithmetic</option><option value="66"> Combinatorics</option><option value="67"> Group Theory/Burnside's lemma</option><option value="68"> Counting</option><option value="69"> Probability/Expected Value</option><option value="70"> Others</option><option value="71"> Tricky</option><option value="72"> Hardest</option><option value="73"> Unusual</option><option value="74"> Brute Force</option><option value="75"> Implementation</option><option value="76"> Constructive Algorithms</option><option value="77"> Two Pointer</option><option value="78"> Bitmask</option><option value="79"> Beginner</option><option value="80"> Discrete Logarithm/Shank's Baby-step Giant-step Algorithm</option><option value="82"> Greedy</option><option value="83"> Divide and Conquer</option><option value="81"> Dynamic Programming</option></select> <button class="ui-button ui-widget ui-state-default ui-button-icon-only ui-corner-right ui-button-icon" style="font-family:'Trebuchet MS', Helvetica, Arial, sans-serif;font-size:1.1em;border-width:1px;border-style:solid;border-color:rgb(204,204,204);font-weight:bold;color:rgb(51,131,187);overflow:visible;" title="Show All Items" type="button"> </button> <button class="ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" style="font-family:'Trebuchet MS', Helvetica, Arial, sans-serif;font-size:1.1em;border-width:1px;border-style:solid;border-color:rgb(204,204,204);font-weight:bold;color:rgb(51,131,187);overflow:visible;" type="submit"> Tag it! </button>

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

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

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

Input

第一行是一个正整数 $T(\leq 5)$ ，表示测试数据的组数，

对于每组测试数据，

第一行是两个整数 $n,q(1\leq n,q \leq 100000)$ ，分别表示节点数和询问数，

接下来 n-1 行，每行包含两个整数 $x,y(1\leq x,y \leq n)$ ，表示和之间有一条边相连，保证这些边能构成一棵树，

接下来行，每行包含三个整数 $A,B,C(1 \leq A,B,C \leq n)$ ，表示一个询问，其中是何老师所在位置，是SK同学所在位置，是小Q同学所在位置，保证小Q同学初始不在教务处。

Output

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

Sample Input

Sample Output

YES
NO

Source

第十五届北京师范大学程序设计竞赛决赛

Author

题目大意：

给你一棵树跟节点是1，q次询问，，每次循环给出三个数 ABC 现在有一个人从B出发到达C再从C出发到达A，另一个人从A出发来拦截他，A，B同时出发，，问能否可以拦截B，当同时到达1时算拦截失败

题目思路：

很好想到的一个是分别求出从B->C->1的路程bc 和 A->1 的路程a 如果 bc<a则一定拦截不了如果bc>a则一定可以拦截到，，如果bc=a 如果最后从C出发到达1和A不在同一颗子树上则拦截失败，也就是lca(A,C)==1时拦截失败，否则在到达1之前A可以拦截上，，对于求距离我们可以用lca来求

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5;
struct nod
{
    int v,w;
    nod(int v,int w):v(v),w(w){}
    nod(){}
};
vector<nod>G[maxn];
int val[maxn],R[maxn],first[maxn],vis[maxn];
int dp[maxn][20];
int n,m,q,tot;
void dfs(int u,int dep)         //将树处理成线性的即每两个节点位于一段连续的区间里
{
    val[++tot] = u,first[u] =tot,R[tot] = dep;
    vis[u] = 1;
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i].v,w = G[u][i].w;
        if(!vis[v])
        {
            dfs(v,dep+1);
            val[++tot] = u,R[tot] = dep;
        }
    }
}
void ST()             //ST预处理
{
    for(int i=1;i<=tot;i++)
        dp[i][0] = i;
    for(int j=1;j<=log(tot)/log(2);j++)
        for(int i=1;i<=tot;i++)
            if(i+(1<<j)-1<=tot)
            {
                int a = dp[i][j-1],b = dp[i+(1<<(j-1))][j-1];
                dp[i][j] = (R[a]<R[b]?a:b);             //保存编号
            }
}
int RMQ(int l,int r)    //求编号
{
    int k=0;
    while((1<<(k+1))<=r-l+1)
        k++;
    int a = dp[l][k],b = dp[r-(1<<k)+1][k];
    return (R[a]<R[b]?a:b);
}
int lca(int u,int v)   //求lca
{
    int x = first[u],y = first[v];
    if(x>y)swap(x,y);
    int res = RMQ(x,y);
    return val[res];    //返回lca
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&q);
        tot = 0;
        for(int i=1;i<=n;i++)
            G[i].clear(),vis[i] = 0;
        for(int i=1;i<n;i++)
        {
            int x,y,z;scanf("%d%d",&x,&y);
            G[x].push_back(nod(y,1));
            G[y].push_back(nod(x,1));
        }
        dfs(1,1);
        ST();
        while(q--)
        {
            int a,b,c;scanf("%d%d%d",&a,&b,&c);
            int lbc = lca(b,c);
            int lac = lca(a,c);
            int len1 = R[first[b]]+R[first[c]]*2-R[first[lbc]]*2-R[1];
            int len2 = R[first[a]] - R[1];
            if(len1<len2||len1==len2&&lac==1)printf("NO\n");
            else printf("YES\n");
        }
    }
    return 0;
}