bnu52509-LCA

向右看齐 2022-06-17 12:19 119阅读 0赞

题目链接：[bnu52509][]

# Borrow Classroom #

Time Limit: 5000ms

Memory Limit: 262144KB

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

[Prev][]  [Submit][]  [Status][]  [Statistics][]  [Discuss][]  [Next][]

Font Size:  \+   \-

Type:

None

Graph Theory

2-SAT

Articulation/Bridge/Biconnected Component

Cycles/Topological Sorting/Strongly Connected Component

Shortest Path

Bellman Ford

Dijkstra/Floyd Warshall

Euler Trail/Circuit

Heavy-Light Decomposition

Minimum Spanning Tree

Stable Marriage Problem

Trees

Directed Minimum Spanning Tree

Flow/Matching

Graph Matching

Bipartite Matching

Hopcroft–Karp Bipartite Matching

Weighted Bipartite Matching/Hungarian Algorithm

Flow

Max Flow/Min Cut

Min Cost Max Flow

DFS-like

Backtracking with Pruning/Branch and Bound

Basic Recursion

IDA\* Search

Parsing/Grammar

Breadth First Search/Depth First Search

Advanced Search Techniques

Binary Search/Bisection

Ternary Search

Geometry

Basic Geometry

Computational Geometry

Convex Hull

Pick's Theorem

Game Theory

Green Hackenbush/Colon Principle/Fusion Principle

Nim

Sprague-Grundy Number

Matrix

Gaussian Elimination

Matrix Exponentiation

Data Structures

Basic Data Structures

Binary Indexed Tree

Binary Search Tree

Hashing

Orthogonal Range Search

Range Minimum Query/Lowest Common Ancestor

Segment Tree/Interval Tree

Trie Tree

Sorting

Disjoint Set

String

Aho Corasick

Knuth-Morris-Pratt

Suffix Array/Suffix Tree

Math

Basic Math

Big Integer Arithmetic

Number Theory

Chinese Remainder Theorem

Extended Euclid

Inclusion/Exclusion

Modular Arithmetic

Combinatorics

Group Theory/Burnside's lemma

Counting

Probability/Expected Value

Others

Tricky

Hardest

Unusual

Brute Force

Implementation

Constructive Algorithms

Two Pointer

Bitmask

Beginner

Discrete Logarithm/Shank's Baby-step Giant-step Algorithm

Greedy

Divide and Conquer

Dynamic Programming

Tag it!

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

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

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

## Input ##

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

对于每组测试数据，

第一行是两个整数![n,q(1\\leq n,q \\leq 100000)][n_q_1_leq n_q _leq 100000]，分别表示节点数和询问数，

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

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

## Output ##

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

## Sample Input ##

1
    7 2
    1 2
    2 3
    3 4
    4 7
    1 5
    1 6
    3 5 6
    7 5 6

## Sample Output ##

YES
    NO

## Source ##

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

## 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;
    }

[bnu52509]: https://www.bnuoj.com/bnuoj/problem_show.php?pid=52509
[Prev]: https://www.bnuoj.com/bnuoj/problem_show.php?pid=52508
[Submit]: https://www.bnuoj.com/bnuoj/problem_show.php?pid=52509#
[Status]: https://www.bnuoj.com/bnuoj/status.php?showpid=52509
[Statistics]: https://www.bnuoj.com/bnuoj/problem_stat.php?pid=52509
[Discuss]: https://www.bnuoj.com/bnuoj/discuss.php?pid=52509
[Next]: https://www.bnuoj.com/bnuoj/problem_show.php?pid=52510
[n]: https://www.bnuoj.com/bnuoj/latexrender/pictures/7b8b965ad4bca0e41ab51de7b31363a1.png
[1]: https://www.bnuoj.com/bnuoj/latexrender/pictures/c4ca4238a0b923820dcc509a6f75849b.png
[q]: https://www.bnuoj.com/bnuoj/latexrender/pictures/7694f4a66316e53c8cdd9d9954bd611d.png
[B]: https://www.bnuoj.com/bnuoj/latexrender/pictures/9d5ed678fe57bcca610140957afab571.png
[C]: https://www.bnuoj.com/bnuoj/latexrender/pictures/0d61f8370cad1d412f80b84d143e1257.png
[A]: https://www.bnuoj.com/bnuoj/latexrender/pictures/7fc56270e7a70fa81a5935b72eacbe29.png
[T_leq 5]: https://www.bnuoj.com/bnuoj/latexrender/pictures/ca7e8f1d2bddbbfd77e45c355a7868da.png
[n_q_1_leq n_q _leq 100000]: https://www.bnuoj.com/bnuoj/latexrender/pictures/25ae998c68bbfab5f1cbea8511646444.png
[n-1]: https://www.bnuoj.com/bnuoj/latexrender/pictures/a438673491daae8148eae77373b6a467.png
[x_y_1_leq x_y _leq n]: https://www.bnuoj.com/bnuoj/latexrender/pictures/8f1ff64b39bc1ea2709f2004eef84ace.png
[x]: https://www.bnuoj.com/bnuoj/latexrender/pictures/9dd4e461268c8034f5c8564e155c67a6.png
[y]: https://www.bnuoj.com/bnuoj/latexrender/pictures/415290769594460e2e485922904f345d.png
[A_B_C_1 _leq A_B_C _leq n]: https://www.bnuoj.com/bnuoj/latexrender/pictures/b7d2a0d55f7b596feae3ff994050220d.png
[Link 1]: https://www.bnuoj.com/bnuoj/problem.php?search=%E7%AC%AC%E5%8D%81%E4%BA%94%E5%B1%8A%E5%8C%97%E4%BA%AC%E5%B8%88%E8%8C%83%E5%A4%A7%E5%AD%A6%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E7%AB%9E%E8%B5%9B%E5%86%B3%E8%B5%9B