#10wa
查看原帖
#10wa
733650
我梦见一片焦土楼主2023/11/1 17:19
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
const long long INF=0x3f3f3f3f;
int n,m,heads[N],tos[N<<1],ww[N<<1],nes[N<<1],ids,dfn[N],h[N<<1],len,cnt,dep[N],st[N][20],st_e[N][20],fa[N],now[N<<2],head[N],to[N<<1],w[N<<1],ne[N<<1],id,dp[N],lens;
bool vis[N];
void adds(int x,int y,int z){
	tos[++ids]=y;
	ww[ids]=z;
	nes[ids]=heads[x];
	heads[x]=ids;
}
void dfs(int u,int f){
	dfn[u]=++cnt;
	fa[u]=f;
	dep[u]=dep[f]+1;
	st_e[u][0]=f;
	for(int i=1;i<20;i++){
		st_e[u][i]=st_e[st_e[u][i-1]][i-1];
		st[u][i]=min(st[u][i-1],st[st_e[u][i-1]][i-1]);
	}
	for(int i=heads[u];i;i=nes[i]){
		int v=tos[i];
		if(v==f){
			continue;
		}
		st[v][0]=ww[i];
		dfs(v,u);
	}
}
bool cmp(int a,int b){
	return dfn[a]<dfn[b];
}
void add(int x,int y,int z){
	to[++id]=y;
	w[id]=z;
	ne[id]=head[x];
	head[x]=id;
}
int lca(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	for(int i=19;i>=0;i--){
		if(dep[st_e[x][i]]>=dep[y]){
			x=st_e[x][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=19;i>=0;i--){
		if(st_e[x][i]!=st_e[y][i]){
			x=st_e[x][i];
			y=st_e[y][i];
		}
	}
	return st_e[x][0];
}
int find(int x,int y){
	int ans=2147483647;
	for(int i=19;i>=0;i--){
		if(dep[x]<=dep[y]){
			ans=min(ans,st[y][i]);
			y=st_e[y][i];
		}
	}
	return ans;
}
void build_tree(){
	sort(h+1,h+len+1,cmp);
	h[0]=1;
	lens=0;
	for(int i=1;i<=len;i++){
		now[++lens]=lca(h[i-1],h[i]);
		now[++lens]=h[i];
	}
	sort(now+1,now+lens+1,cmp);
	lens=unique(now+1,now+lens+1)-now-1;
	for(int i=2;i<=lens;i++){	
		int k=lca(now[i-1],now[i]);
		if(vis[k]&&k!=1){
			continue;
		}
		int wp=find(k,now[i]);
		add(k,now[i],wp);
		add(now[i],k,wp);
	}	
}
void dfs_dp(int u,int f,int num){
	dp[u]=num;
	if(vis[u]){
		return;
	}
	int anss=0;
	for(int i=head[u];i;i=ne[i]){
		int v=to[i];
		if(v==f){
			continue;	
		}
		dfs_dp(v,u,w[i]);
		anss+=dp[v];
	}
	if(anss){
		dp[u]=min(dp[u],anss);
	}
}
void init(){
	id=0;
	for(int i=0;i<=lens;i++){
		int s=now[i];
		head[s]=ne[2*i]=ne[2*i-1]=vis[s]=0;
	}
}
signed main(){
	memset(st,0x3f,sizeof st);
	cin>>n;
	for(int i=1,x,y,z;i<n;i++){
		cin>>x>>y>>z;
		adds(x,y,z);
		adds(y,x,z);
	}
	dfs(1,0);
	cin>>m; 
	while(m--){
		cin>>len;
		for(int i=1;i<=len;i++){
			cin>>h[i];
			vis[h[i]]=1;
		}
		build_tree();
		dfs_dp(1,0,INF);
		cout<<dp[1]<<endl;
		init();
	}
	return 0;
}
2023/11/1 17:19
加载中...