RT
如果过早了的话紫衫
思路代码注释里有
请问各位大佬这个思路是哪里假了还是本质就是错的
望指明或者给几组便于调试的 Hack 数据,感激不尽
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int Maxn = 420;
namespace Basic {
template <typename Temp> inline void read(Temp & res) {
Temp fh = 1; res = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
res = res * fh;
}
template <typename Temp> inline void Checkmax(Temp & res, Temp comp) {if(comp > res) res = comp;}
template <typename Temp> inline void Checkmin(Temp & res, Temp comp) {if(comp < res) res = comp;}
}
using namespace Basic;
using namespace std;
/*
首先一遍的 dfs 求出在所有的子树中遍历所有有草莓的节点并回到初始节点的所用的最小时间
然后再跑树形背包。
直接设 f[u][i] 表示第二个人在以 u 为根的子树上可以为第一个人省下的最多时间。
特别的当决定把某棵子树走完的时候,第一个人直接不进入这颗子树,还有额外的 2 点贡献。
预处理 tim[u] 表示在以 u 为根的子树上直接遍历所有关键节点所花费的最小时间。
最终答案即为 max(i,tim[1] - f[1][i]) 的最小值。
*/
struct e {
int to, nxt;
} b[Maxn << 1];
int ecnt, head[Maxn];
void add(int u, int v) {b[++ecnt] = (e){v, head[u]}; head[u] = ecnt;}
int tim[Maxn], f[Maxn][Maxn << 1];
bool bl[Maxn];
int n, m;
void dfs0(int t, int fa) {
for(int i = head[t]; i; i = b[i].nxt) {
int tto = b[i].to;
if(tto == fa) continue;
dfs0(tto, t);
if(bl[tto]) {
bl[t] = 1;
tim[t] = tim[t] + tim[tto] + 2;
}
}
}
int g[Maxn][Maxn << 2]; //在前 i 颗子树里花费 j 秒钟可以省下的最多时间。
void dfs1(int t, int fa) {
//cerr << t << endl;
memset(g, 0, sizeof(g));
int cnt = 0;
for(int i = head[t]; i; i = b[i].nxt) {
int tto = b[i].to; if(tto == fa) continue;
cnt++; dfs1(tto, t);
for(int j = 0; j <= tim[t]; j += 2) {
g[cnt][j] = g[cnt - 1][j];
if(j >= tim[tto] + 2) Checkmax(g[cnt][j], g[cnt - 1][j - tim[tto] - 2] + tim[tto] + 2);
for(int k = 2; k <= min(tim[tto] + 2, j); k += 2) {
Checkmax(g[cnt][j], g[cnt - 1][j - k] + f[tto][k - 2]);
}
}
}
for(int i = 0; i <= tim[t]; i += 2) f[t][i] = g[cnt][i];
}
int x, y, ans = 0x7fffffff;
int main() {
read(n); read(m);
for(int i = 1; i < n; ++i) {
read(x); read(y);
add(x, y); add(y, x);
}
for(int i = 1; i <= m; ++i) {
read(x); bl[x] = 1;
}
dfs0(1, 0); dfs1(1, 0);
for(int i = 0; i <= tim[1]; i += 2) {
Checkmin(ans, max(i, tim[1] - f[1][i]));
}
printf("%d", ans);
return 0;
}