[蓝桥杯][2018年第九届真题]版本分支（离线LCA模板）

题目描述 小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。 现在这个项目的代码一共有N个版本，编号1~N，其中1号版本是最初的版本。 除了1号版本之外，其他版本的代码都恰好有一个直接的父版本；即这N个版本形成了一棵以1为根的树形结构。

如下图就是一个可能的版本树：

1

/ 2 3 | / 5 4 6

现在小明需要经常检查版本x是不是版本y的祖先版本。你能帮助小明吗？

输入 第一行包含两个整数N和Q，代表版本总数和查询总数。 以下N-1行，每行包含2个整数u和v，代表版本u是版本v的直接父版本。 再之后Q行，每行包含2个整数x和y，代表询问版本x是不是版本y的祖先版本。 输出 对于每个询问，输出YES或NO代表x是否是y的祖先。

样例输入 6 5 1 2 1 3 2 5 3 6 3 4 1 1 1 4 2 6 5 2 6 4 样例输出 YES YES NO NO NO 这个题是真的狗，时间卡的很严。在线LCA算法TLE了。单纯的离线LCA也会TLE，但是比在线的过的样例多。我是用的离线LCA+快读，然后才过的。题目本身不难，就是一个LCA，算是模板了。 代码如下：

#include<bits/stdc++.h>
#define ll long long
#define Pll pair<int,int>
using namespace std;

const int MAXN = 1e5+100;
struct node{
          
   
	int y,id;
	node (int a,int b)
	{
          
   
		y=a,id=b;
	}
};
vector<node> vec[MAXN];
bool vis[MAXN];
int per[MAXN],head[MAXN],in_num[MAXN],ans[MAXN],a[MAXN];
map<Pll,int> mp;
int cnt,n,m;
 
struct Node
{
          
   
 int c,next;
}edge[MAXN];

inline int read() {
          
   
    char ch = getchar(); int x = 0, f = 1;
    while(ch < 0 || ch > 9) {
          
   
        if(ch == -) f = -1;
        ch = getchar();
    } while(0 <= ch && ch <= 9) {
          
   
        x = x * 10 + ch - 0;
        ch = getchar();
    } return x * f;
}

void Init()
{
          
   
 cnt = 0;
 memset(in_num,0,sizeof(in_num));
 memset(head,-1,sizeof(head));
 memset(vis,0,sizeof(vis));
    for(int i =1;i <= n;i++)
    {
          
   
          vec[i].clear();
          per[i] = i;
    }
}
 
void add(int x,int y)
{
          
   
    edge[++cnt].next = head[x];
    edge[cnt].c = y;
    head[x] = cnt;
}
 
int Find(int x)
{
          
   
    if(per[x] != x)
          per[x] = Find(per[x]);
    return per[x];
}
 
void Union(int x,int y)
{
          
   
    x = Find(x);y = Find(y);
    if(x == y)
          return ;
    per[x] = y;
}
 
void Tarjan(int x)
{
          
   
    for(int i = head[x];i != -1; i =edge[i].next)
    {
          
   
        int v = edge[i].c;
        Tarjan(v);
        Union(v,x);
    }
    vis[x] = 1;
    for(int i = 0;i < vec[x].size();i ++)
        if(vis[vec[x][i].y]) ans[vec[x][i].id]=Find(vec[x][i].y);
}
int main()
{
          
   
    int x,y;
    n=read(),m=read();
    Init();
    for(int i = 1;i < n;i++)
    {
          
   
        x=read(),y=read();
        add(x,y);
        in_num[y] ++;
    }
    for(int i = 0;i < m;i ++)
    {
          
   
        x=read(),y=read();
        vec[x].push_back(node(y,i));
        vec[y].push_back(node(x,i));
        a[i]=x;
    }
    int root;
    root=1;
    Tarjan(root);
    for(int i=0;i<m;i++)
    {
          
   
    	if(a[i]!=ans[i]) printf("NO
");
    	else printf("YES
");
	}
	return 0;
}

努力加油a啊，(o)/~