题目链接：https://cn.vjudge.net/problem/Gym-101630L
题目大意：
对于一个集合的集合，若其中任意两个集合 \(A\) 和 \(B\) 都满足下述三个条件之一：\(A \subset B\) 或 \(B \subset A\) 或 \(A \cap B = \varnothing\)，则称这个集合 \(laminar\).
给定一棵有 \(N\) 个结点的树，再给出 \(f\) 个集合，每个集合包含树上两点之间的最短路径所经过的所有点，问这 \(f\) 个集合所组成的集合是否 \(laminar\).
知识点： LCA、树上差分前缀和
解题思路：
首先，所有只包含一个点的集合都可以忽略，它们不影响答案。
用树上差分前缀和求出各个点被多少条路径经过（即被多少个集合包含）。
忽略所有没有被集合包含的点，那么剩下的点的度数不能大于 \(2\)，即剩下的图都是链。对于每一条链，维护一个单调栈来验证是否满足 \(laminar\) 即可。
AC代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn = 100000+5,DEG=20;
4
5 /******LCA******/
6 int fa[maxn][DEG];
7 int deg[maxn];
8 vector<int> G[maxn];
9 void BFS(int root){
10 queue<int> que;
11 deg[root]=0;
12 fa[root][0]=root;
13 que.push(root);
14 while(!que.empty()){
15 int tmp=que.front();
16 que.pop();
17 for(int i=1;i<DEG;i++)
18 fa[tmp][i]=fa[fa[tmp][i-1]][i-1];
19 for(int i=0;i<G[tmp].size();i++){
20 int v=G[tmp][i];
21 if(v==fa[tmp][0]) continue;
22 deg[v]=deg[tmp]+1;
23 fa[v][0]=tmp;
24 que.push(v);
25 }
26 }
27 }
28 int LCA(int u,int v){
29 if(deg[u]>deg[v]) swap(u,v);
30 int hu=deg[u],hv=deg[v];
31 int tu=u,tv=v;
32 for(int det=hv-hu,i=0;det;det>>=1,i++){
33 if(det&1)
34 tv=fa[tv][i];
35 }
36 if(tu==tv) return tu;
37 for(int i=DEG-1;i>=0;i--){
38 if(fa[tu][i]==fa[tv][i])
39 continue;
40 tu=fa[tu][i];
41 tv=fa[tv][i];
42 }
43 return fa[tu][0];
44 }
45
46
47 struct Path{
48 int u,v,len;
49 }pth[maxn]; //记录路径
50 int cnt=0;
51 bool cmp(const Path &a,const Path &b){
52 if(a.len>b.len) return true;
53 return false;
54 }
55
56 /******树上差分前缀和******/
57 int val[maxn];
58 void dfs1(int rt,int last){
59 for(int i=0;i<G[rt].size();i++){
60 int to=G[rt][i];
61 if(to!=last){
62 dfs1(to,rt);
63 val[rt]+=val[to];
64 }
65 }
66 }
67
68 int du[maxn];
69
70 bool vis[maxn];
71 vector<int> Next[maxn];
72 int que[maxn],indx[maxn];
73 stack<int> endpt;
74 bool check(int s){
75 int tot=0;
76 int now=s;
77 while(1){//对链上的点进行编号
78 vis[now]=true;
79 bool flag=false;
80 indx[now]=tot;
81 que[tot++]=now;
82 for(int i=0;i<G[now].size();i++){
83 int to=G[now][i];
84 if(val[to]&&!vis[to]){
85 now=to;
86 flag=true;
87 break;
88 }
89 }
90 if(!flag) break;
91 }
92 while(!endpt.empty()) endpt.pop();
93 for(int i=0;i<tot;i++){
94 //单调栈维护结束结点的编号（对于每一条路径，编号小的是开始结点，编号大的是结束结点）
95 while(!endpt.empty()&&endpt.top()<i) endpt.pop();
96 int now=que[i];
97 for(int j=0;j<Next[now].size();j++){
98 int to=Next[now][j];
99 if(indx[to]>i){
100 if(endpt.empty()||indx[to]<=endpt.top()) endpt.push(indx[to]);
101 else return false; //检查是否满足条件
102 }
103 }
104 }
105 return true;
106 }
107
108 int main(){
109 // freopen("in.txt","r",stdin);
110 int n,f;
111 scanf("%d%d",&n,&f);
112 for(int i=1;i<n;i++){
113 int u,v;
114 scanf("%d%d",&u,&v);
115 G[u].push_back(v);
116 G[v].push_back(u);
117 }
118 BFS(1);
119 for(int i=0;i<f;i++){
120 int u,v;
121 scanf("%d%d",&u,&v);
122 if(u==v) continue;
123 pth[cnt].u=u,pth[cnt].v=v;
124 int tfa=LCA(u,v);
125 pth[cnt].len=deg[u]+deg[v]-2*deg[tfa];
126 val[u]++,val[v]++,val[tfa]--;
127 if(tfa!=1) val[fa[tfa][0]]--;
128 cnt++;
129 }
130 dfs1(1,1);
131 for(int i=1;i<=n;i++){
132 if(!val[i]) continue;
133 for(int j=0;j<G[i].size();j++){
134 if(val[G[i][j]]) du[i]++; //计算每一个有被路径经过的结点的度数
135 }
136 }
137 for(int i=1;i<=n;i++){
138 if(du[i]>2){
139 printf("No\n");
140 return 0;
141 }
142 }
143 sort(pth,pth+cnt,cmp);
144 for(int i=0;i<cnt;i++){
145 Next[pth[i].u].push_back(pth[i].v); //记录路径
146 Next[pth[i].v].push_back(pth[i].u);
147 }
148 for(int i=1;i<=n;i++){
149 if(du[i]==1&&!vis[i]){
150 if(!check(i)){
151 printf("No\n");
152 return 0;
153 }
154 }
155 }
156 printf("Yes\n");
157 return 0;
158 }