题意：
删除价值和最小的边使得$1$号点与$k$个关键点不连通
一个树形DP...但是询问多次，保证总的关键点数为$O(n)$
先说一下这个$DP$
$f[i]$表示子树$i$中的关键点与$1$不连通的最小价值
如果$i$是关键点则必须删除$i$到$1$的权值最小的边，否则$sum f[child of i]$
学了一下虚树...找不到别的资料啊只有别人的$Blog$
试验了好多写法
貌似其中有好多带$Bug$的写法
最终定下了现在的版本应该是没大有问题的吧...明天再做两道虚树，有问题再来改
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N=3e5+5; const ll INF=1e18; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,Q,u,v,op,w; int root; struct Edge{ int v,ne,w; }e[N<<1]; int cnt,h[N]; inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt; } inline void ins2(int u,int v){ cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt; } int size[N],mx[N],top[N],dfn[N],dfc,deep[N],fa[N]; ll mn[N]; void dfs(int u){ size[u]++; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(v==fa[u]) continue; deep[v]=deep[u]+1; fa[v]=u; mn[v]=min(mn[u],(ll)e[i].w); dfs(v); size[u]+=size[v]; if(size[v]>size[mx[u]]) mx[u]=v; } } void dfs2(int u,int anc){ dfn[u]=++dfc;top[u]=anc; if(mx[u]) dfs2(mx[u],anc); for(int i=h[u];i;i=e[i].ne) if(e[i].v!=fa[u] && e[i].v!=mx[u]) dfs2(e[i].v,e[i].v); } int lca(int x,int y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]]) swap(x,y); x=fa[top[x]]; } return deep[x]<deep[y] ? x : y; } int a[N],st[N]; inline bool cmp(int x,int y){return dfn[x]<dfn[y];} ll f[N]; int key[N]; ll dp(int u){ ll t=0; for(int i=h[u];i;i=e[i].ne) t+=dp(e[i].v); if(key[u]) f[u]=mn[u]; else f[u]=min(mn[u],t); h[u]=0; return f[u]; } void solve(){ cnt=0; n=read(); for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+1+n,cmp); //int p=0; //a[++p]=a[1]; //for(int i=2;i<=n;i++) // if(lca(a[p],a[i])!=a[p]) a[++p]=a[i]; //n=p; for(int i=1;i<=n;i++) key[a[i]]=1; int top=0; for(int i=1;i<=n;i++){ if(!top){st[++top]=a[i];continue;} int u=a[i],f=lca(u,st[top]); while(dfn[f]<dfn[st[top]]){ if(dfn[f]>=dfn[st[top-1]]){ ins2(f,st[top--]); if(st[top]!=f) st[++top]=f; break; }else ins2(st[top-1],st[top]),top--; } st[++top]=u; } while(top!=1) ins2(st[top-1],st[top]),top--; dp(st[1]); for(int i=1;i<=n;i++) key[a[i]]=0; printf("%lld ",f[st[1]]); } int main(){ freopen("in","r",stdin); n=read(); for(int i=1;i<=n-1;i++) u=read(),v=read(),w=read(),ins(u,v,w); mn[1]=INF;dfs(1);dfs2(1,1); Q=read(); memset(h,0,sizeof(h));cnt=0; while(Q--) solve(); }