題目描述
小明負(fù)責(zé)維護(hù)公司一個(gè)奇怪的項(xiàng)目。這個(gè)項(xiàng)目的代碼一直在不斷分支(branch)但是從未發(fā)生過合并(merge)。
現(xiàn)在這個(gè)項(xiàng)目的代碼一共有N個(gè)版本，編號(hào)1~N，其中1號(hào)版本是最初的版本。
除了1號(hào)版本之外，其他版本的代碼都恰好有一個(gè)直接的父版本；即這N個(gè)版本形成了一棵以1為根的樹形結(jié)構(gòu)。

如下圖就是一個(gè)可能的版本樹：

1

/
2 3
| /
5 4 6

現(xiàn)在小明需要經(jīng)常檢查版本x是不是版本y的祖先版本。你能幫助小明嗎？

輸入
第一行包含兩個(gè)整數(shù)N和Q，代表版本總數(shù)和查詢總數(shù)。
以下N-1行，每行包含2個(gè)整數(shù)u和v，代表版本u是版本v的直接父版本。
再之后Q行，每行包含2個(gè)整數(shù)x和y，代表詢問版本x是不是版本y的祖先版本。
輸出
對(duì)于每個(gè)詢問，輸出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
這個(gè)題是真的狗，時(shí)間卡的很嚴(yán)。在線LCA算法TLE了。單純的離線LCA也會(huì)TLE，但是比在線的過的樣例多。我是用的離線LCA+快讀，然后才過的。題目本身不難，就是一個(gè)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\n");else printf("YES\n");}return 0; }

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

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][2018年第九届真题]版本分支（离线LCA模板）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。