LCA -cogs2098 [SYOI 2015] Asm.Def的病毒

题目链接：http://cogs.pro:8081/cogs/problem/problem.php?pid=vQXmxVaPU

【题目描述】

“这就是我们最新研制的，世界上第一种可持久化动态计算机病毒，‘创世纪’。”方教授介绍道。

“哦。”主席面无表情地点点头。

“‘创世纪’无法真正杀死透明计算网络，但是可以把它变成傻子。可惜透明计算网络能轻松地辨认出病毒，所以我建议……”

“为什么不伪装呢？”Asm.Def说。

“当然不行，它比我们更懂伪装。”

“我是说，把我们的病毒伪装成杀毒软件。”

方教授震惊地盯着Asm.Def看了一会。“你是个天才。”

Asm.Def想把病毒伪装成杀毒软件，入侵透明计算网络。透明计算网络的文件结构是一棵N个节点的树，每个病毒可以入侵一条路径上的所有节点。但如果两个病毒入侵了同一个节点，由于它们伪装成了杀毒软件，就会自相残杀。Asm.Def不希望这样的情况发生，所以他需要仔细制定入侵计划。为此，他需要频繁地询问，两条路径是否经过同一个节点（即是否相交）。

【输入格式】

第一行两个整数N,Q。

接下来N-1行，每行两个整数a,b，表示(a,b)是树上的一条边。

接下来Q行，每行四个整数s1,t1,s2,t2，表示询问s1~t1的路径是否与s2~t2的路径相交。

【输出格式】

对每个询问，若相交则输出一行”YES”，否则输出一行”NO”。

【样例输入】

【样例输出】

NO

YES

NO

NO

YES

【提示】

N,Q<=1000.

1<=s1,t1,s2,t2<=N。

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <cstring>

#define MAXN 1010

using namespace std;

struct edge

{

    int to;

    edge* pre;

    edge() :to(), pre(NULL) {};

}e[MAXN << ];

int n, q;

int s1, t1, s2, t2;

int a, b, cnt = ;

edge* preV[MAXN] = { NULL };                //preV[n]用于取以n为起点的边的地址，依次更新，如果链式遍历每个以n为起点的边

int p[MAXN] = {  };                        //p[n] 为n的父亲节点

bool vis[MAXN << ];

void insert(int a, int b)

{

    e[cnt].to = b;

    e[cnt].pre = preV[a];

    preV[a] = &e[cnt++];

}

void dfs(int x)             //遍历处理p数组

{

    int y;

    for (edge* ee = preV[x]; ee; ee = ee->pre)

    {

        y = ee->to;

        if (y == p[x])

            continue ;

        p[y] = x;

        dfs(y);

    }

}

int LCA(int x, int y)       //找到x和y的lca

{

    memset(vis, , sizeof(vis));

    while (x)

    {

        vis[x] = true;

        x = p[x];

    }

    while (y)

    {

        if(vis[y])

            return y;

        y = p[y];

    }

    return x;

}

int query(int lca, int s, int t) //查询lca是否在s和t的路径上

{

    int l = LCA(s, t);

    do

    {

        if (lca == s)              //判断是否lca就是节点s

            return true;

        if (s == l)              //判断节点s是否是s和t的lca

            break;

        s = p[s];                 //往上走

    } while (s);

    /*不能用while的原因是：如果s刚好就等于L，无法进入循环，就无法对于lca==s返回true，如果将s==l放后边，则s = p[s]就把s转移了*/

    while (t && t != l)

    {

        if (lca == t)

            return true;

        t = p[t];

    }

    return false;

}

int main()

{

    //freopen("asm_virus.in", "r", stdin);

    //freopen("asm_virus.out", "w", stdout);

    scanf("%d %d", &n, &q);

    for (int i = ; i < n; i++)

    {

        scanf("%d %d", &a, &b);

        insert(a, b);

        insert(b, a);

    }

    dfs();

    int firLCA, secLCA;

    while (q--)

    {

        scanf("%d %d %d %d", &s1, &t1, &s2, &t2);

        firLCA = LCA(s1, t1);

        secLCA = LCA(s2, t2);

        if (query(firLCA, s2, t2) || query(secLCA, s1, t1))

            cout << "YES" << endl;

        else

            cout << "NO" << endl;

    }

    return ;

}

巴特西