2098. [SYOI 2015] Asm.Def的病毒

★☆ 输入文件：asm_virus.in 输出文件：asm_virus.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

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

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

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

“为什么不伪装呢？”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。

【来源】

“Asm.Def战记之夏威夷”杯

这一题的题面看起来可真是好玩啊

这一道题真是一个神奇的题

题意就是判断一下两条路径是否相交而且还要多次询问所以必须要有一格效率很高的方法不能暴力

这一道题的标签看起来好可怕！LCA！？？？满脸疑惑

哈哈↑↑题面都在斗图我也来一个

所以这一道题到底跟LCA有什么关系呢？

。。。。（沉默中）

我默默地翻了一下别人的代码

终于发现了奥妙所在

别急别急我们来看一个图吧（本图借用自weixin_34362991）

这一道题的思路是这个样子的

就是说有两条路径 2-6 and 5-3 很显然是相交的（看到那个3了吗！！！）

首先我们把能看到的lca瞅一遍

lca(2,6)=1

lca(3,5)=6

很显然这个时候6的深度是要比1的深度要大的

那我们就取6为"LLCCAA"

LLCCAA和2的lca是1

LLCCAA和6的lca是6

这个6和LLCCAA相等所以他们是相交的（好神奇！？）

其实也肥肠好理解

就是说这条lca更深的路径的lca 与较浅的路径的两个端点的lca如果有其中的任何一个与更深路径的两个端点的lca的lca等于更深路径两个端点的lca 就是香蕉了

也就是说相当于这一条更浅得路延伸到了这条更深的路的lca的下面也就是相交了嘛

（↑是不是很简单）

自己结合那个图觉悟一会就明白了哦

太开心了！3分钟A样例随之AC~（尽管树链剖分那一段是复制的啦啦啦(～￣▽￣)～）

本人拙见如有疏漏之处敬请指正

代码如下树链剖分一波：

#include<bits/stdc++.h>

#define maxn 1005

using namespace std;

int n,Ques;

vector<int> v[maxn];

int size[maxn],dfn[maxn],pos[maxn],vis[maxn],fa[maxn],son[maxn],top[maxn],dep[maxn];

int cnt=;

void Dfs(int x)

{

    size[x]=;//首先以x为根的子树的大小size  先设为1  就是目前已x为根的子树只有x自己

    for(int i=;i<v[x].size();i++)

    {

        int y=v[x][i];//son

        if(!size[y])//这里的意思其实就是如果这个儿子还没有访问过

        //因为我们可以看到每一次dfs的开始才会把size设一个数值 一开始应该都是0的

        //所以这里就可以直接当做一个vis标记用了

        {

            dep[y]=dep[x]+;//记录深度 son的深度 是father的深度+1

            fa[y]=x;//记录son的father 是谁

            Dfs(y);

            size[x]+=size[y];//更新x为根的子树的大小

            if(size[son[x]]<size[y])//son存储的是重儿子

                son[x]=y;//更新重儿子

        }

    }

}

void Dfs(int x,int tp)

{

    top[x]=tp;//top数组是用来记录一条重链的顶端

    dfn[++cnt]=x;//dfn是记录第cnt个访问的点是x

    pos[x]=cnt;//pos记录第x个点是第cnt个访问的  当然在本题中不会用到

    if(son[x])//如果有重儿子 先走重儿子

        Dfs(son[x],tp);

    for(int i=;i<v[x].size();i++)

    {

        int y=v[x][i];

        if(!top[y])//走轻儿子

            Dfs(y,y);

    }

}

int lca(int x,int y)

{

    while(top[x]!=top[y])//先跳到同一条重链上

    {

        if(dep[top[x]]<dep[top[y]])

            swap(x,y);

        x=fa[top[x]];

    }

    if(dep[x]>dep[y])//保证x的深度更小  x就是lca

        swap(x,y);

    return x;

}

inline int read()

{

    int X=; bool flag=; char ch=getchar();

    while(ch<''||ch>'') {if(ch=='-') flag=; ch=getchar();}

    while(ch>=''&&ch<='') {X=(X<<)+(X<<)+ch-''; ch=getchar();}

    if(flag) return X;

    return ~(X-);

}

int main()

{

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

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

    n=read(),Ques=read();

    for(int i=,x,y;i<n;i++)

    {

        x=read(),y=read();

        v[x].push_back(y);

        v[y].push_back(x);

    }

    Dfs();Dfs(,);

    for(int i=,x,y,u,v;i<=Ques;i++)

    {

        x=read(),y=read(),u=read(),v=read();

        int lca1=lca(x,y),lca2=lca(u,v);

        if(dep[lca1]<dep[lca2]) swap(lca1,lca2),swap(x,u),swap(y,v);

        if(lca(lca1,u)==lca1||lca(lca1,v)==lca1)

            puts("YES");

        else

            puts("NO");

    }

    return ;

}

巴特西

cogs 2098. [SYOI 2015] Asm.Def的病毒 LCA 求两条路径是否相交