D
树从叶子到根，对于某个点，如果其子树不存在需要的点，那么这个点和它的父亲所连的边，自然不需要，否则需要。
有一个问题，比如需要点2、4、5，那么点1和点2所连的边也算进去了。实际上，到了它们的LCS（最大公共祖先）后，这些边就不用算了。用一个变量统计当前遍历过多少需要的点，如果所有需要的点恰好都遍历过了，那么当前遍历的点为LCS，直接退出即可。
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define ULL unsigned long long
5
6 const LL mod_1=1e9+7;
7 const LL mod_2=998244353;
8
9 const double eps_1=1e-5;
10 const double eps_2=1e-10;
11
12 const int maxn=2e5+10;
13
14 vector<int> adj[maxn];
15 bool vis[maxn];
16 int k,r=0,value[maxn];
17
18 void dfs(int d)
19 {
20 vis[d]=1;
21 for (auto dd:adj[d])
22 if (!vis[dd])
23 {
24 dfs(dd);
25 value[d]+=value[dd];
26 }
27 if (value[d]>0)
28 r++;
29 if (value[d]==k)
30 {
31 cout<<r;
32 exit(0);
33 }
34 }
35
36 int main()
37 {
38 int n,i,a,b;
39 cin>>n>>k;
40 for (i=1;i<n;i++)
41 {
42 cin>>a>>b;
43 adj[a].push_back(b);
44 adj[b].push_back(a);
45 }
46 memset(value,0,sizeof(value));
47 for (i=1;i<=k;i++)
48 {
49 cin>>a;
50 value[a]=1;
51 }
52 memset(vis,0,sizeof(vis));
53 dfs(1);
54 return 0;
55 }
E
T(到达时间)从小到大排序。 对于某一项，先确定X的值（即这一趟至少要延迟多长时间）：对于这一站的起始城市Aj，即上一趟转乘的到达城市Bi(Aj=Bi)，找到城市Bi中到达时间(Ti)<=这一项的出发时间(Sj)中，到达+延迟时间最大(Ti+Xi)的，然后和这一项的出发时间(Sj)做比较，取max，从而也获得了这一项的X的值，X=max( max{Ti+Xi} - Sj, 0)。 然后对于这一项的到达城市Bj，更新对于城市Bj，到达 / 到达+延迟时间的信息(记录第一个是到达时间，记录第二个对应的到达+延迟时间，城市Bj的这两项信息按到达时间从小到大的排序)。 X0也有可能在非首位(T最小)的位置
实际上，这道题挺好写的，不难。最少人做和做对，估计是：
1. 题意长，题面看着繁琐（挺多公式、变量），比较难懂，劝退了不少人
2. 实际上写方法、代码，也比较绕
3. G相对好做，大家先做了G
无法理解这么多WA，是因为它们没有考虑“X0也有可能在非首位(T最小)的位置”，这个？
TLE不少，难道是它们都尝试暴力做？或者是有什么"环“？？没有对T进行排序？
1 /*
2 T(到达时间)从小到大排序。
3 对于某一项，先确定X的值（即这一趟至少要延迟多长时间）：对于这一站的起始城市Aj，即上一趟转乘的到达城市Bi(Aj=Bi)，找到城市Bi中到达时间(Ti)<=这一项的出发时间(Sj)中，到达+延迟时间最大(Ti+Xi)的，然后和这一项的出发时间(Sj)做比较，取max，从而也获得了这一项的X的值，X=max( max{Ti+Xi} - Sj, 0)。
4 然后对于这一项的到达城市Bj，更新对于城市Bj，到达 / 到达+延迟时间的信息(记录第一个是到达时间，记录第二个对应的到达+延迟时间，城市Bj的这两项信息按到达时间从小到大的排序)。
5 X0也有可能在非首位(T最小)的位置
6 */
7 #include <bits/stdc++.h>
8 using namespace std;
9 #define LL long long
10 #define ULL unsigned long long
11
12 const LL mod_1=1e9+7;
13 const LL mod_2=998244353;
14
15 const double eps_1=1e-5;
16 const double eps_2=1e-10;
17
18 const int maxn=2e5+10;
19
20 LL x[maxn];
21 //a[maxn],b[maxn],s[maxn],t[maxn]
22 struct node
23 {
24 LL a,b,s,t,index;
25 bool operator<(node v)
26 {
27 return t < v.t;
28 }
29 } info[maxn];
30
31 vector<LL> lat[maxn], tim[maxn];
32
33 int main()
34 {
35 LL n,m,i,a,b,add;
36 memset(x,0,sizeof(x));
37 cin>>n>>m>>x[1];
38 for (i=1;i<=m;i++)
39 {
40 //cin>>a[i]>>b[i]>>s[i]>>t[i];
41 cin>>info[i].a>>info[i].b>>info[i].s>>info[i].t;
42 info[i].index=i;
43 }
44 sort(info+1,info+m+1);
45
46 //cout<<"test "<<info[1].t<<endl;
47
48 for (i=1;i<=m;i++)
49 if (info[i].index==1)
50 break;
51
52 b = info[i].b;
53 tim[b].push_back( info[i].t );
54 lat[b].push_back( info[i].t + x[1] );
55
56 while (i<=m)
57 {
58 i++;
59
60 a = info[i].a;
61 auto it = upper_bound(tim[a].begin(), tim[a].end(), info[i].s);
62 if (it==tim[a].begin())
63 continue;
64
65 it--;
66 add = max( *(it-tim[a].begin() + lat[a].begin()) - info[i].s , 0LL);
67 x[ info[i].index ] = add;
68
69 if (add!=0)
70 {
71 b = info[i].b;
72 if (lat[b].empty() || lat[b].back() < info[i].t + add)
73 {
74 tim[b].push_back(info[i].t);
75 lat[b].push_back(info[i].t+add);
76 }
77 }
78 }
79
80 for (i=2;i<=m;i++)
81 {
82 cout<<x[i];
83 if (i!=m)
84 cout<<" ";
85 }
86
87 return 0;
88 }
F
这么多人做和做对，严重怀疑用了chatgpt，emmm。现在数论题，感觉chatgpt很容易搜出正确方法。
实际上，vscode自动补全了很多代码。
【算法模板】博弈论：尼姆博弈定理与SG定理_grundy 数-CSDN博客
G
标签：info,const,LL,value,ABC368,maxn,long From： https://www.cnblogs.com/cmyg/p/18383198