Tree Queries

题意： 给出树上的一些点，判断这些点中某些是否可以连成一条到根的路径，并且剩余的点到这条路径的距离为 1 . 原文：

You are given m queries. The i-th query consists of the set of ki distinct vertices vi[1],vi[2],…,vi[ki]. Your task is to say if there is a path from the root to some vertex u such that each of the given k vertices is either belongs to this path or has the distance 1 to some vertex of this path.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
10 6
1 2
1 3
1 4
2 5
2 6
3 7
7 8
7 9
9 10
4 3 8 9 10
3 2 4 6
3 2 1 5
3 4 8 2
2 6 10
3 5 4 7

output

1
2
3
4
5
6
YES
YES
YES
YES
NO
NO

1

思路一：选出深度最深的点 v ，显然所有的点要么属于 v 到根节点的路径，要么到这条路径的距离为 1. 可以先找出这条路径，在这条路径上的点去除; 对于剩下的点 ki ,求 ki ，v 的最近公共祖先 u, 如果 ki 到 u 的距离 = 1，那么这点是符合的，依次判断。

思路二：（膜大佬代码orz）同思路一用 lca ,但是不求路径。对于所有的 ki , 根据深度排序。如果要符合题目要求，相邻的 ki, kj 的 lca 只能为 ki ,kj, ki 的父节点，kj 的父节点四种情况之一。否则就不符合。

思路三： (官方题解) 因为不在路径（最深的点到根节点的路径）上的点到路径上的距离只能等于 1， 所以如果这样的点直接用它的父节点替代，然后再判断所有点是否都在路径上即可。

如何判断所有的点是否都在一条路径上？

  • 路径上相邻的点 u,v , lca(u ,v) = u or v ,(有点像思路一)

  • 跑一边 dfs 记录所有点第一次访问的时间 tin, 和最后一次访问的时间 tout ,

    如果 $tin_v≤tin_u ,tout_u≤tout_v $ u 是 v 的祖先节点。如果所有的点都是最深的节点的父节点，那么所有点都在一条路径上 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const int MAX=200000+10;
int n,m,u,v,flag;
int anc[MAX][22],l[MAX],k,tmp;
vi g[MAX],ki;
void dfs(int u,int fa){
	fi(i,0,g[u].size()){
		int v=g[u][i];
		if(v==fa) continue;
		l[v]=l[u]+1;
		anc[v][0]=u;
		fi(j,1,20) anc[v][j]=-1;
		dfs(v,u);
	}
}
int lca(int p,int q){
	if(l[p]<l[q]) swap(p,q);  //p 深 
	for(int i=20;i>=0;i--) { //p q 同深度
		if(anc[p][i]!=-1 && l[anc[p][i]]>=l[q])
			p=anc[p][i];
	}
	if(p==q) return p;//  返回两者离祖先的最近距离 
	for(int i=20;i>=0;i--)
		if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
			p=anc[p][i];q=anc[q][i];   //向上
		}
	return anc[p][0];
}
int cmp(int a,int b){
	return l[a]<l[b];
}
int main(){
//	freopen("in","r",stdin);
	mem(anc,-1);
	sf(n);sf(m);
	fi(i,0,n-1){
		sf(u);sf(v);
		g[u].pb(v);
		g[v].pb(u);
	}
	l[1]=1;
	dfs(1,-1);
	fi(j,1,20)
		fi(i,1,n+1)	if(anc[i][j-1]!=-1)
			anc[i][j]=anc[anc[i][j-1]][j-1]; 
	fi(i,0,m){
		sf(k);
		ki.clear();
		fi(i,0,k){
			sf(tmp);
			ki.pb(tmp);
		}
		sort(all(ki),cmp);
		flag=0;
		fi(i,1,k){
			int u= ki[i-1],v=ki[i];
			int w=lca(u,v);
			if(w!=u&&w!=v&&w!=anc[u][0]&&w!=anc[v][0]){
				flag=1;break;
			}
		}
		if(flag) pfc("NO\n");
		else pfc("YES\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//题解代码
#include <bits/stdc++.h>
using namespace std;
int T;
vector<int> p, d;
vector<int> tin, tout;
vector<vector<int>> g;

void dfs(int v, int par = -1, int dep = 0) {
	p[v] = par;
	d[v] = dep;
	tin[v] = T++;
	for (auto to : g[v]) {
		if (to == par) continue;
		dfs(to, v, dep + 1);
	}
	tout[v] = T++;
}
bool isAnc(int v, int u) {
	return tin[v] <= tin[u] && tout[u] <= tout[v];
}
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif	
	int n, m;
	cin >> n >> m;
	T = 0;
	p = d = vector<int>(n);
	tin = tout = vector<int>(n);
	g = vector<vector<int>>(n);
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(0);	
	for (int i = 0; i < m; ++i) {
		int k;
		cin >> k;
		vector<int> v(k);
		for (auto &it : v) {
			cin >> it;
			--it;
		}		
		int u = v[0];
		for (auto it : v) if (d[u] < d[it]) u = it;
		for (auto &it : v) {
			if (it == u) continue;
			if (p[it] != -1) it = p[it];
		}
		bool ok = true;
		for (auto it : v) ok &= isAnc(it, u);
		if (ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}