题目大意：给定一棵 N 个节点的有根树，1 号节点为根节点，树边有两个权值，分别为走路的代价和开车的代价。有一个旅行者开车要从根节点出发，必须遍历给定点集，可以在任何位置停止旅行，有车时可以选择开车或步行，没车只能跑路，求最小代价。
题解：这是我做过最恶心的树形dp QAQ
和 apple tree 这道题很相似，只不过这次是多了车这个东西。因此，在设计状态的时候要考虑到人和车的关系，dp[u][0] 表示人走到以 u 为根的子树中必须返回的最小权值，dp[u][1] 表示人下去但是不一定上来的最小代价，dp[u][2] 表示人和车都可以下去，人和车都必须上来的最小代价，dp[u][3] 表示人和车可以下去，人上来车不一定上来的最小代价，dp[u][4] 表示人和车可以下去，但是人和车都不一定上来的最小代价。
dp[u][0-3] 的转移方程比较好想，对于最后一种情况来说，分为走最后一棵子树的时候有没有车，如果没有车就意味着在之前遍历的某棵子树中只有人回来了，因此需要考虑两棵子树对答案的贡献。可是发现，两棵子树显然不能是同一棵，因此需要记录下最优解和次优解，以及取得最优解的是哪颗子树，这样才能合并两棵子树的贡献。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
typedef long long LL;
int n,m,key[maxn];
LL dp[maxn][5];
struct node{int nxt,to;LL w0,w1;}e[maxn<<1]; // w0 -> walk w1 -> car
int tot=1,head[maxn];
inline void add_edge(int from,int to,LL w0,LL w1){
e[++tot]=node{head[from],to,w0,w1},head[from]=tot;
}
void dfs(int u,int fa){
LL d1=0,d3=0,d4=0;
LL fi1=1e18,se1=1e18,fi2=1e18,se2=1e18; // fi1 -> dp[v][3]+w0+w1 fi2 -> dp[v][1]+w0
int x=0,y=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to; LL w0=e[i].w0,w1=e[i].w1;
if(v==fa)continue;
dfs(v,u);
key[u]+=key[v];
if(key[v]){
LL t=min(dp[v][0]+2*w0,dp[v][2]+2*w1);
dp[u][0]+=dp[v][0]+2*w0;
dp[u][2]+=t;
d1=min(d1,dp[v][1]-dp[v][0]-w0);
d3=min(d3,dp[v][3]+w0+w1-t);
d4=min(d4,min(dp[v][4]+w1,dp[v][1]+w0)-t);
LL ret1=dp[v][3]+w0+w1-t;
if(ret1<fi1)se1=fi1,fi1=ret1,x=v;
else se1=min(se1,ret1);
LL ret2=dp[v][1]+w0-t;
if(ret2<fi2)se2=fi2,fi2=ret2,y=v;
else se2=min(se2,ret2);
}
}
if(x&&y){
if(x!=y)d4=min(d4,fi1+fi2);
else d4=min(d4,min(fi1+se2,fi2+se1));
}
dp[u][1]=dp[u][0]+d1;
dp[u][3]=dp[u][2]+d3;
dp[u][4]=dp[u][2]+d4;
}
void read_and_parse(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int x,y,w0,w1;
scanf("%d%d%d%d",&x,&y,&w0,&w1);
add_edge(x,y,w0,w1),add_edge(y,x,w0,w1);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x;scanf("%d",&x);
key[x]++;
}
}
void solve(){
dfs(1,0);
printf("%lld
",dp[1][4]);
}
int main(){
read_and_parse();
solve();
return 0;
}