本身求答案是简单的树上DP，只需要求出根到每个点路径上的最小值，然后考虑割连父亲的边还是割所有儿子即可，但是每次都这样做一次显然不能通过，考虑优化
用虚树来优化：虚树是针对树上一些点建出来的一棵树，上面只有这些点和它们的LCA。显然这样虚树的大小不会超过2*所选点数，这样在缩小了问题规模的同时还保留了原树的性质。
具体的建法：
0.预处理DFS序
1.将所选点按DFS序从小到大排序
2.用栈维护一条从根延伸下来的链，依次将排序后的点nde加入。若栈为空则直接入栈，否则设栈顶为top：
3.求nde和top的lca，讨论：
①lca是top，直接跑路
②lca不是top，设栈顶起第二个元素为sec。在lca的DFS序不大于sec时不断将sec与top相连并弹栈
之后如果lca仍然不是top，连接lca与top，将lca入栈
将nde入栈
(因为我们按DFS序排序，所以不可能是nde)
之后就可以愉快地树形DP辣
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int N=500005;
6 int T,n,m,t1,t2,t3,cnt,Cnt,tot,poi;
7 int P[N],Noww[N],Goal[N],p[N],noww[N],goal[N],val[N];
8 int siz[N],far[N],dep[N],imp[N],top[N],dfn[N],pts[N],stk[N];
9 long long mini[N],dp[N];
10 bool cmp(int a,int b)
11 {
12 return dfn[a]<dfn[b];
13 }
14 void Link(int f,int t,int v)
15 {
16 noww[++cnt]=p[f],p[f]=cnt;
17 goal[cnt]=t,val[cnt]=v;
18 noww[++cnt]=p[t],p[t]=cnt;
19 goal[cnt]=f,val[cnt]=v;
20 }
21 void Linka(int f,int t)
22 {
23 Noww[++Cnt]=P[f];
24 Goal[Cnt]=t,P[f]=Cnt;
25 Noww[++Cnt]=P[t];
26 Goal[Cnt]=f,P[t]=Cnt;
27 }
28 void i207M()
29 {
30 Cnt=0,stk[poi=1]=1;
31 }
32 void DFS(int nde,int fth,int dth)
33 {
34 int tmp=0;
35 siz[nde]=1,far[nde]=fth,dep[nde]=dth;
36 for(int i=p[nde];i;i=noww[i])
37 if(goal[i]!=fth)
38 {
39 mini[goal[i]]=min(mini[nde],1ll*val[i]);
40 DFS(goal[i],nde,dth+1);
41 siz[nde]+=siz[goal[i]];
42 if(siz[goal[i]]>tmp)
43 tmp=siz[goal[i]],imp[nde]=goal[i];
44 }
45 }
46 void Mark(int nde,int tpp)
47 {
48 top[nde]=tpp,dfn[nde]=++tot;
49 if(imp[nde])
50 {
51 Mark(imp[nde],tpp);
52 for(int i=p[nde];i;i=noww[i])
53 if(goal[i]!=far[nde]&&goal[i]!=imp[nde])
54 Mark(goal[i],goal[i]);
55 }
56 }
57 int LCA(int x,int y)
58 {
59 while(top[x]!=top[y])
60 {
61 if(dep[top[x]]<dep[top[y]])
62 swap(x,y); x=far[top[x]];
63 }
64 return dep[x]<dep[y]?x:y;
65 }
66 void Insert(int nde)
67 {
68 if(poi==1) stk[++poi]=nde;
69 else
70 {
71 int lca=LCA(nde,stk[poi]);
72 if(lca==stk[poi]) return;
73 while(poi>1&&dfn[lca]<=dfn[stk[poi-1]])
74 Linka(stk[poi-1],stk[poi]),poi--;
75 if(lca!=stk[poi])
76 Linka(lca,stk[poi]),stk[poi]=lca;
77 stk[++poi]=nde;
78 }
79 }
80 void Getans(int nde,int fth)
81 {
82 long long tmp=-1;
83 dp[nde]=mini[nde];
84 for(int i=P[nde];i;i=Noww[i])
85 if(Goal[i]!=fth)
86 Getans(Goal[i],nde),tmp+=dp[Goal[i]];
87 P[nde]=0; if(~tmp) dp[nde]=min(dp[nde],tmp+1);
88 }
89 int main()
90 {
91 scanf("%d",&n);
92 for(int i=1;i<n;i++)
93 scanf("%d%d%d",&t1,&t2,&t3),Link(t1,t2,t3);
94 for(int i=1;i<=n;i++) mini[i]=1e12;
95 DFS(1,0,1),Mark(1,1);
96 scanf("%d",&T);
97 while(T--)
98 {
99 scanf("%d",&m),i207M();
100 for(int i=1;i<=m;i++) scanf("%d",&pts[i]);
101 sort(pts+1,pts+1+m,cmp);
102 for(int i=1;i<=m;i++) Insert(pts[i]);
103 while(poi>1) Linka(stk[poi],stk[poi-1]),poi--;
104 Getans(1,0),printf("%lld\n",dp[1]);
105 }
106 return 0;
107 }
View Code