学习：chenhuan001
模板借鉴：自为风月马前卒
虚树模板题：P2495 [SDOI2011]消耗战
思路：裸虚树题，建好虚树后直接在虚树上树形dp即可。
#include<bits/stdc++.h> #define ll long long #define P pair<int,int> #define mk make_pair using namespace std; const int maxn=3e5+10; ll mn[maxn]; int sz[maxn],son[maxn],top[maxn],id[maxn],dep[maxn]; int a[maxn],s[maxn],f[maxn],cnt,Top; vector<P>G[maxn]; vector<int>G2[maxn]; bool cmp(int x,int y) { return id[x]<id[y]; } void dfs1(int u,int fa,int deep) { f[u]=fa; dep[u]=deep; sz[u]=1; for(auto tmp : G[u]) { int v = tmp.first; if (v == fa) continue; mn[v]=min(mn[u], 1ll*tmp.second); dfs1(v,u,deep+1); sz[u]+=sz[v]; if(sz[v]>sz[son[u]]) son[u]=v; } } void dfs2(int u,int rt) { top[u]=rt; id[u]=++cnt; if(son[u]) dfs2(son[u],rt); for(auto tmp : G[u]) { int v = tmp.first; if (v != f[u] && v != son[u]) dfs2(v,v); } } int LCA(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); x=f[top[x]]; } if(dep[x] > dep[y]) swap(x,y); return x; } void add(int x,int y) { G2[x].push_back(y); } void insert(int x) { if (Top == 1) { s[++Top] = x; return; } int lca = LCA(s[Top], x); if (lca == s[Top]) return; while (Top > 1 && id[s[Top-1]] >= id[lca]) add(s[Top-1], s[Top]),Top--; if (lca != s[Top]) add(lca, s[Top]), s[Top]=lca; s[++Top] = x; } ll dfs(int u) { if (G2[u].size() == 0) return mn[u]; ll res = 0; for (auto v : G2[u]) res += dfs(v); G2[u].clear(); return min(res, mn[u]); } int main() { int n,m,k,u,v,w; scanf("%d",&n); for (int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); G[u].push_back(mk(v,w)); G[v].push_back(mk(u,w)); } mn[1]=1e18; dfs1(1,0,1); dfs2(1,1); scanf("%d",&m); while(m--) { scanf("%d",&k); for (int i = 1; i <= k; ++i) scanf("%d",&a[i]); sort(a+1, a+1+k, cmp); s[Top = 1] = 1; for (int i = 1; i <= k; ++i) insert(a[i]); while (Top > 1) add(s[Top - 1], s[Top]),Top--; printf("%lld\n",dfs(1)); } }
