P2495
话说虚树，咳咳
这个题就是虚树+树形DP+单调栈+LCA的完美结合
因为代码上基本每行都有注释，所以直接上：
#include <bits/stdc++.h>
using namespace std;
int n,q,dx[500005],de[500005],fa[500005][25],m[500005],b[500005],h,tp,dfn = 1;
int a[500005],st[500005],hd1[500005],cnt1 = 1,hd2[500005],cnt2 = 1;
long long dp[500005];
struct edge
{
int to,nt;
long long v;
}e1[1000005],e2[1000005];
/*
变量
n：岛屿数量
q：询问次数
h：关键点数量
tp：栈顶编号
dfn：DFS序计数器
cnt1：初始图计数器
cnt2：虚树计数器
to：邻节点
nt：下一条边
v：代价
数组
dx：DFS序
de：节点深度
fa：点i跳2^j个祖先后的位置
m：存倍增跳的次数
b：是否为关键点
a：关键点
st：虚树的右链（栈）
hd1：表示初始图以i为起点的最后一条边的储存位置
hd2：表示虚树以i为起点的最后一条边的储存位置
dp：预处理，1~i路径上最小边权和
e1：存初始图
e2：存虚树
*/
void add1(int x,int y,long long v)//链式前向星存初始图
{
e1[cnt1].nt = hd1[x];
e1[cnt1].to = y;
e1[cnt1].v = v;
hd1[x] = cnt1++;
}
void add2(int x,int y)//链式前向星存虚树
{
e2[cnt2].nt = hd2[x];
e2[cnt2].to = y;
hd2[x] = cnt2++;
}
void dfs1(int x)//作用在main里调用时写了
{
int k;//用于初始化的变量
for(k = 0;fa[x][k] != 0;k++)//当跳2^k个祖先后还在图上
{
fa[x][k + 1] = fa[fa[x][k]][k];//跳第2^(k+1)个祖先=跳两次2^k个祖先
}
m[x] = k;//记录结果
dx[x] = dfn++;//计算DFS序
for(int i = hd1[x];i != 0;i = e1[i].nt)//从hd1[x]开始遍历初始图
{
int to = e1[i].to;//i的邻节点
if(dx[to] == 0)//是否已计算过（因为如果计算过DFS序就不是0）
{
de[to] = de[x] + 1;//邻节点的DFS等于x的+1
dp[to] = min(dp[x],e1[i].v);//dp的DP初始化
fa[to][0] = x;//邻节点跳1次就是x
dfs1(to);//继续dfs
}
}
}
long long dfs2(int x)//DP求1~x的最小边权和
{
long long sum = 0,mina;//sum计算子节点的边权和，mina是最终结果
for(int i = hd2[x];i != 0;i = e2[i].nt)//从hd2[x]开始遍历虚树
{
int to = e2[i].to;//i的邻节点
sum += dfs2(to);//sum加上to的最小边权和
}
if(b[x] == 1)//如果x是关键点
{
mina = dp[x];//最终结果就是1~x的最小边权和
}
else
{
mina = min(dp[x],sum);//取1~x的最小边权和，与x的所有子节点的边权和的最小值
}
b[x] = 0;//清空虚树
hd2[x] = 0;//同上
return mina;//返回结果
}
int lca(int x,int y)//求x和y的最近公共祖先
{
if(de[x] < de[y])//如果x的深度比y的小
{
swap(x,y);//因为lca函数是假设x的深度不小于y的，所以交换
}
/*
%：从2的尽可能大的次幂去找，一旦能找到能接近x,y的i，就更新de[x]，直到相等。
类似于无限逼近，最后值相等的过程。如果i相等了，就说明x,y的深度已经在同一层了。
*/
for(int i = m[x];i >= 0;i--)//i从x最多能倍增的数量递减到0，从大到小是因为%
{
if(de[fa[x][i]] >= de[y])//如果x跳2^i次后的点的深度还不小于y的深度
{
x = fa[x][i];//更新x，变成跳2^i次后的点（倍增）
}
}
if(x == y)//如果x和y相等了
{
return x;//这时x是已经跳过多次的，y没变，所以当前的x一定是初始x的祖先
}
//现在x和y不相等
for(int i = m[x];i >= 0;i--)//i从x最多能倍增的数量递减到0
{
if(fa[x][i] != fa[y][i])//如果x跳2^i次和y跳2^i次后的点不一样
{
x = fa[x][i];//更新x（倍增）
y = fa[y][i];//更新y（倍增）
}
}
//成功让x和y变成某个点z的两个子节点
return fa[x][0];//随便找一个的父节点输出
}
int cmp(int x,int y)//按照DFS序给点排序
{
return dx[x] < dx[y];//x的DFS序小于y的
}
int main()
{
dp[1] = 0x3f3f3f3f3f3f3f3f;//初始化
scanf("%d",&n);
for(int i = 1;i <= n - 1;i++)
{
int x,y;//岛屿x到y有一条路径
long long w;//代价是w
scanf("%d%d%lld",&x,&y,&w);
add1(x,y,w);//连边
add1(y,x,w);//反过来
}
dfs1(1);
/*
dfs1函数干了什么：
1.求出lca函数用的倍增数组fa
2.求出每个点的深度和DFS序
3.求出每个点到根这条路径上的最小边权
*/
scanf("%d",&q);
while(q--)
{
scanf("%d",&h);
for(int i = 1;i <= h;i++)
{
scanf("%d",&a[i]);
b[a[i]] = 1;//在b数组中记录关键点
}
sort(a + 1,a + h + 1,cmp);//将关键点按照DFS序排序
tp = 1;//栈顶编号初值为1
st[1] = a[1];//栈底设为第一个关键点
for(int i = 2;i <= h;i++)//遍历下标为2~h的关键点
{
int x = a[i],lc = lca(a[i],st[tp]);//x为关键点，lc是关键点和栈顶的LCA
while(true)//循环
{
if(de[lc] >= de[st[tp - 1]])//LCA的深度不小于栈里次大的点的深度
{
if(lc != st[tp])//如果LCA不等于栈顶节点
{
add2(lc,st[tp]);//虚树连边LCA和栈顶节点
if(lc != st[tp - 1])//如果LCA不等于栈里次大点
{
st[tp] = lc;//栈顶成为LCA
}
else
{
tp--;//栈顶编号-1，等同于将栈顶弹出
}
}
break;
}
add2(st[tp - 1],st[tp]);//虚树连边栈顶和栈里次大的点
tp--;//栈顶编号-1，将栈顶弹出
}
st[++tp] = x;//将关键点入栈
}
while(--tp)//遍历
{
add2(st[tp],st[tp + 1]);//将右链（栈）里相邻的点连边
}
printf("%lld\n",dfs2(st[1]));//从栈底开始dfs求答案（栈底就是a[1]）
cnt2 = 1;//为下一次询问作准备
}
return 0;
}这个题对我来说很难，想要弄懂自己打出来更难，所以就借鉴了题解，然后深度理解+每行自己注释，终于完全懂了！