题目大意：
给出一个无向无环连通图（树），n个点n-1条边，m次查询，每次询问给出一个集合，问集合里的树是否都在同一条链上（即能否不重复的走一条边而遍历整个点集）
思路：通过求lca，若有三个点x,y,z
如果满足dix(x,y)+dix(y,z) == dix(x,z)，说明此时y位于x,z之间，此时他们就在一条链上，只需要枚举除x,y以外剩下的n-2个点
判断是否满足类似的条件，每次不断跟新x,y的值使其成为一条链上的两个端点。
1 # include<iostream>
2 # include<bits/stdc++.h>
3 using namespace std;
4 const int N = 2e5 + 10;
5 int h[N], e[2 * N], ne[2 * N], idx;
6 int depth[N], fa[N][25];
7 int dis[N];
8 void bfs(int root)/*预处理depth和fa*/
{
9 memset(depth, 0x3f, sizeof depth);
10 queue<int> q;
11 q.push(root);
12 depth[0] = 0,depth[root] = 1;
13 while (q.size()) {
14 int t = q.front();
15 q.pop();
16 for (int i = h[t]; i != -1; i = ne[i]) {
17 int j = e[i];
18 if (depth[j] > depth[t] + 1) {
19 depth[j] = depth[t] + 1;
20 dis[j] = dis[t] + 1;
21 q.push(j);
22 fa[j][0] = t;
23 for (int k = 1; k <= 20; ++k) {
24 fa[j][k] = fa[fa[j][k - 1]][k - 1];
25 }
26 }
27 }
28 }
29 }
30
31 int lca(int a, int b) {/*倍增求lca（最近公共祖先）*/
32 if (depth[a] < depth[b]) swap(a, b);
33 for (int i = 20; i >= 0; --i) {
34 if (depth[fa[a][i]] >= depth[b]) a = fa[a][i];
35 }
36 if (a == b) return a;
37 for (int i = 20; i >= 0; --i) {
38 if (fa[a][i] != fa[b][i]) {
39 a = fa[a][i];
40 b = fa[b][i];
41 }
42 }
43 return fa[a][0];
44 }
45
46 void add(int a, int b) {
47 e[idx] = b;
48 ne[idx] = h[a];
49 h[a] = idx++;
50 }
51 int getdis(int x, int y) {/*两点之间最短距离*/
52 return dis[x] + dis[y] - 2 * dis[lca(x, y)];
53 }
54
55 void solve() {
56 int n;
57 bool ok = 1;
58 cin >> n;
59 if (n == 1 || n == 2) {
60 for (int i = 1; i <= n; ++i) {
61 int x;
62 cin >> x;
63 }
64 cout << "YES" << endl;
65 return;
66 }
67 int x, y;
68 cin >> x >> y;
69 for (int i = 3; i <= n; ++i) {
70 int z;
71 cin >> z;
72 if (getdis(x, z) + getdis(z, y) == getdis(x, y)) continue;
73 if (getdis(x, y) + getdis(y, z) == getdis(x, z)) {
74 y = z;
75 continue;
76 }
77 if (getdis(y, x) + getdis(x, z) == getdis(y, z)) {
78 x = z;
79 continue;
80 }
81 ok = false;
82 }
83 if (ok) cout << "YES" << endl;
84 else cout << "NO" << endl;
85 }
86 int tt;
87
88 int main() {
89
90 int n;
91 cin >> n;
92 memset(h, -1, sizeof h);
93 for (int i = 1; i < n; ++i) {
94 int a, b;
95 cin >> a >> b;
96 add(a, b), add(b, a);
97 }
98 bfs(1);
99 // for(int i = h[1];i!=-1;i = ne[i]) cout<<e[i]<<" ";
100 cin>>tt;
101 while(tt--)solve();
102 return 0;
103 }
