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的祖先版本。  

對于30%的資料，1 <= N <= 1000  1 <= Q <= 1000  

對于100%的資料，1 <= N <= 100000  1 <= Q <= 100000  

輸出

----

對于每個詢問，輸出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

#include <bits/stdc++.h>
using namespace std;

const int maxn=10010;//頂點數
const int maxq=100;//最多查詢次數，根據題目而定，本題中其實每組資料隻有一個查詢.

//并查集
int f[maxn];//根節點
int find(int x)
{
    if(f[x]==-1)
        return x;
    return f[x]=find(f[x]);
}
void unite(int u,int v)
{
    int x=find(u);
    int y=find(v);
    if(x!=y)
        f[x]=y;
}
//并查集結束

bool vis[maxn];//節點是否通路
int ancestor[maxn];//節點i的祖先
struct Edge
{
    int to,next;
}edge[maxn*2];
int head[maxn],tot;
void addedge(int u,int v)//鄰接表頭插法加邊
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}

struct Query
{
    int q,next;
    int index;//查詢編号，也就是輸入的順序
}query[maxq*2];
int ans[maxn*2];//存儲每次查詢的結果,下表0~Q-1，其實應該開maxq大小的。
int h[maxn],tt;
int Q;//題目中需要查詢的次數

void addquery(int u,int v,int index)//鄰接表頭插法加詢問
{
    query[tt].q=v;
    query[tt].next=h[u];
    query[tt].index=index;
    h[u]=tt++;
    query[tt].q=u;//相當于兩次查詢，比如查詢  3，5 和5，3結果是一樣的，以3為頭節點的鄰接表中有5，以5為頭節點的鄰接表中有3
    query[tt].next=h[v];
    query[tt].index=index;
    h[v]=tt++;
}

void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
    tt=0;
    memset(h,-1,sizeof(h));
    memset(vis,0,sizeof(vis));
    memset(f,-1,sizeof(f));
    memset(ancestor,0,sizeof(ancestor));
}

void LCA(int u)
{
    ancestor[u]=u;
    vis[u]=true;
    for(int i=head[u];i!=-1;i=edge[i].next)//和頂點u相關的頂點
    {
        int v=edge[i].to;
        if(vis[v])
            continue;
        LCA(v);
        unite(u,v);
        ancestor[find(u)]=u;//将u的左右孩子的祖先設為u
    }
    for(int i=h[u];i!=-1;i=query[i].next)//看輸入的查詢裡面有沒有和u節點相關的
    {
        int v=query[i].q;
        if(vis[v])
            ans[query[i].index]=ancestor[find(v)];
    }
}
bool flag[maxn];//用來确定根節點的
int num[100006];
int t;
int n,u,v;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&Q);
        init();
        memset(flag,0,sizeof(flag));
        memset(num,0,sizeof(num));
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            flag[v]=true;//有入度
            addedge(u,v);
            addedge(v,u);
        }
      //  Q=1;//題目中隻有一組查詢

        for(int i=0;i<Q;i++)
        {
            scanf("%d%d",&u,&v);
            addquery(u,v,i);
            num[i]=u;
        }
        int root;
        for(int i=1;i<=n;i++)
        {
            if(!flag[i])
            {
                root=i;
                break;
            }
        }
        LCA(root);
        for(int i=0;i<Q;i++)
            {
                if(num[i]==ans[i])printf("YES\n");
                else printf("NO\n");
            }
    }

    return 0;
}