题目大意
若有一颗带边权的树，且每次询问$k$个节点，问$k$个节点均不与1号节点相连的最小边权。
试题分析
考虑暴力$dp$,设$dp_i$为处理好i的子树的最小边权，我们定义$val_i$为从$i$到根的最小边权，则$dp_i=min(sum dp_v,val_i)$。
但是发现其实有一些节点是没有用的，有用的其实是$lca$。并且发现$sum k_i leq 5 imes 10^5$，所以就可以将树进行简化。
所以就有一个算法诞生了，虚树。我们用欧拉序建出一颗只包含有用节点的树，然后再暴力$dp$就行。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<stack> #define int long long #include<climits> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int N=500001; struct node{ int u,v,w,nex; }x[N<<1]; int val[N],head[N],n,fa[N][21],deep[N],num,in[N],out[N],cnt,q; void dfs(int f,int fath,int W){ val[f]=min(val[fath],W); deep[f]=deep[fath]+1,in[f]=++num; fa[f][0]=fath; for(int i=1;(1<<i)<=deep[f];i++) fa[f][i]=fa[fa[f][i-1]][i-1]; for(int i=head[f];i!=-1;i=x[i].nex){ if(x[i].v==fath) continue; dfs(x[i].v,f,x[i].w); } out[f]=++num; } void add(int u,int v,int w){ x[cnt].u=u,x[cnt].v=v,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++; } int book[N],sta[N]; bool cmp(int x,int y){ int s1,s2; if(x>0) s1=in[x];else s1=out[-x]; if(y>0) s2=in[y];else s2=out[-y]; return s1<s2; } int lca(int u,int v){ if(deep[u]<deep[v]) swap(u,v); for(int i=20;i>=0;i--) if(deep[u]-(1<<i)>=deep[v]) u=fa[u][i]; if(u==v) return u; for(int i=20;i>=0;i--){ if(fa[u][i]==fa[v][i]) continue; u=fa[u][i],v=fa[v][i]; }return fa[u][0]; } stack<int> s; int dp[N]; signed main(){ memset(head,-1,sizeof(head)); n=read();val[0]=LLONG_MAX; for(int i=1;i<n;i++){ int u=read(),v=read(),w=read(); add(u,v,w),add(v,u,w); }q=read(); dfs(1,0,LLONG_MAX); while(q--){ int st=read(); for(int i=1;i<=st;i++) sta[i]=read(),book[sta[i]]=1,dp[sta[i]]=val[sta[i]]; sort(sta+1,sta+st+1,cmp); for(int i=1;i<st;i++){ int Lca=lca(sta[i],sta[i+1]); if(!book[Lca]){book[Lca]=1;sta[++st]=Lca;} } int Now=st; for(int i=1;i<=Now;i++) sta[++st]=-sta[i]; if(!book[1]) sta[++st]=1,sta[++st]=-1; sort(sta+1,sta+st+1,cmp); for(int i=1;i<=st;i++){ if(sta[i]>0) s.push(sta[i]); else{ int f=s.top();s.pop(); if(f!=1){int fath=s.top();dp[fath]+=min(dp[f],val[f]);} else{printf("%lld ",dp[1]);} dp[f]=book[f]=0; } } } }