题目简述
给定一棵 $n$ 个节点的树，有 $k$ 个节点有草莓。两个人同时从 1 号点出发，每一时刻可以不动或者走向相邻的节点，经过到达一个点的时候可以摘到那个点的草莓。至少在第几时刻末，两个人一共可以摘到所有草莓，并且都回到 1 号点。$1≤k≤n≤415$
思路
先把有草莓的点称为关键节点，那么对于一个点：
- 如果这个点是关键节点且其子树中有关键节点，那么取消这个点关键节点的资格，因为要达到下面的关键节点一定要经过这个点，顺便就可以采摘这个点的草莓，对答案没有影响。
- 如果这个点不是关键节点且其子树中没有关键节点，那么这个点就没有用，可以删掉。
现在所有关键节点都是叶节点，并且只有关键节点是叶节点。我们要给两个人分配他们需要经过的关键节点。称一个叶节点集合 $S$ 的代价 $cost_S$ 为包含 1 号点和 $S$ 中每一个点的最小联通块所含边数。这样以来对于两个人分配的关键节点集合 $S_1$ 和 $S_2$，我们就要最小化 $2×\max{cost_{S_1}+cost_{S_2}}$。
考虑如何计算 $cost$，设每个点的深度是 $depth$，那么对于 $S={a_1,a_2,…,a_k},\ cost_S=depth_{a_1} + \Sigma(depth_{a_i}-depth_{LCA(a_i,a_{i-1})})$。因为到达集合内的第一个点一直走下去后，去往下一个点时只需要返回这两个点的 LCA 就可以了。但是不同的两点 LCA 深度可能不同，为了最小化代价，我们在将一系列点加入集合前按照 DFS 序排序，这样可以最大化相邻两点的 LCA 深度和。
设 $f_{i,j,k,l}$ 为考虑到第 $i$ 个关键节点，上一个在两个人分配的集合内的点是 $j,k$，第一个人分配了 $l$ 个点时第二个人集合代价的最小值，于是可以从 $f_{i-1,j,i-1,l},\ f_{i-1,i-1,k,l-1}$ 转移过来。
然而原题这样开数组是开不下的，注意到每次转移时 $j,k$ 中一定有一个是 $i-1$，那么可以将状态修改为 $f_{i,0/1,j,l}$ 表示考虑到第 $i$ 个关键节点，上一个关键节点分给了谁，上一个分配给另外那个人的关键节点是 $j$，第一个人分配了 $l$ 个点时第二个人几个代价的最小值。
然而空间可能还不够用，可以考虑把第一维滚掉或者用 short 代替 int（毕竟没有多少边）。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#include<vector>
#define int short
using namespace std;
const int MaxN = 500;
int n, c, father[MaxN], depth[MaxN], head[MaxN], cntEdge, ans = 0x3f3f;
int stack[MaxN], top;
struct Vertex{
int father, depth, subtreeSize, chainTop, heavySon;
bool berry;
}vertex[MaxN];
#define xTop vertex[x].chainTop
#define yTop vertex[y].chainTop
struct Edge{
int destination, nextEdge;
}edge[MaxN*2];
#define thisSon edge[i].destination
int f[MaxN][MaxN][2][MaxN];
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
int min(int a, int b){return a < b ? a : b;}
int max(int a, int b){return a > b ? a : b;}
inline void AddEdge(int u, int v){
cntEdge++;
edge[cntEdge].destination = v;
edge[cntEdge].nextEdge = head[u];
head[u] = cntEdge;
return;
}
inline bool DFS1(int x, int fa){
// printf("%lld %lld\n", x, vertex[x].berry);
vertex[x].subtreeSize = 1;
vertex[x].father = fa;
vertex[x].depth = vertex[fa].depth+1;
for(int i = head[x]; i; i = edge[i].nextEdge){
if(thisSon == vertex[x].father) continue;
vertex[x].berry &= 1 ^ DFS1(thisSon, x);
// printf("%lld ", vertex[x].berry);
vertex[x].subtreeSize += vertex[thisSon].subtreeSize;
if(vertex[thisSon].subtreeSize > vertex[vertex[x].heavySon].subtreeSize) vertex[x].heavySon = thisSon;
}
// printf("%lld %lld\n", x, vertex[x].berry);
if(vertex[x].berry) stack[++top] = x;
return vertex[x].berry;
}
inline void DFS2(int x, int thisTop){
vertex[x].chainTop = thisTop;
if(!vertex[x].heavySon) return;
DFS2(vertex[x].heavySon, thisTop);
for(int i = head[x]; i; i = edge[i].nextEdge){
if(thisSon == vertex[x].father || thisSon == vertex[x].heavySon) continue;
DFS2(thisSon, thisSon);
}
return;
}
inline int LCA(int x, int y){
while(xTop != yTop){
if(vertex[xTop].depth < vertex[yTop].depth) swap(x,y);
x = vertex[xTop].father;
}
if(vertex[x].depth > vertex[y].depth) swap(x,y);
return x;
}
inline int Value(int x, int y){
x = stack[x], y = stack[y];
if(!x) return (short)vertex[y].depth - 1;
return vertex[y].depth - vertex[LCA(x,y)].depth;
}
inline int &F(int i, int j, int k, int l){
if(j == i-1) return f[i][k][0][l];
return f[i][j][1][l];
}
signed main(){
n = Read(), c = Read();
for(int i=1; i<n; i++){
int u = Read(), v = Read();
AddEdge(u,v);
AddEdge(v,u);
}
for(int i=1; i<=c; i++){
int x = Read();
vertex[x].berry = 1;
}
DFS1(1,0);
DFS2(1,1);
for(int i=0;i<=top+1;i++)
for(int j=0;j<=top;j++)
for(int l=0;l<=n;l++)
f[i][j][0][l] = f[i][j][1][l] = 0x3f3f;
f[1][0][0][0] = f[1][0][1][0] = 0;
for(int i=1; i<=top; i++){
for(int j=0; j<i; j++){
for(int k=(j==i-1? 0 : i-1); k<=i-1; k++){
for(int l=0; l<n; l++){
F(i+1, i, k, l+Value(j,i)) = min(F(i+1, i, k, l+Value(j,i)), F(i,j,k,l));
F(i+1, j, i, l) = min(F(i+1,j,i,l), F(i,j,k,l) + Value(k,i));
}
}
}
}
for(int i=0; i<=top; i++){
for(int j=0; j<n; j++)
ans = min(ans, max(min(F(top+1, i, top, j), F(top+1, top, i, j)), j));
}
cout<<ans*2;
return 0;
}