虚树求调,玄关
查看原帖
虚树求调,玄关
397689
___Furina___楼主2024/8/13 10:31

帮帮萌新吧,过不去样例,玄关:

/*Life is too long to end at a grave*/
#include<bits/stdc++.h>
#define N 500010
#define I_love_Furina return
#define forever 0
#define foreverr 1
#define Endl endl
#define endl '\n'
#define FIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define db double
#define chc cout<<114514<<endl
#define PII pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define inf 191919191919810
#define int long long
using namespace std;
int n,T,m,dfn[N],cnt,dep[N],head[N],head1[N],num1,num,q[N],f[N][21],minn[N],t[N];
bool b[N];
struct edge{int to,nxt,w;}a[N<<1],a1[N<<1];
inline void add(int u,int v,int w){a[++num].to=v,a[num].nxt=head[u],a[num].w=w,head[u]=num;}
inline void add1(int u,int v,int w){a1[++num1].to=v,a1[num1].nxt=head1[u],a1[num1].w=w,head1[u]=num1;}
void dfs(int x,int fa){
	dep[x]=dep[fa]+1,dfn[x]=++cnt,f[x][0]=fa;
	// cout<<x<<":";
	for(int i=1;f[x][i-1];i++)f[x][i]=f[f[x][i-1]][i-1];//,cout<<f[x][i]<<" ";cout<<endl;
	for(int i=head[x];i;i=a[i].nxt){
		int v=a[i].to;
		if(v==fa)continue;
		minn[v]=min(minn[x],a[i].w),dfs(v,x);
	}
}
inline bool cmp(int x,int y){I_love_Furina dfn[x]<dfn[y];}
inline int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
	if(x==y)I_love_Furina x;
	for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	I_love_Furina f[x][0];
}
int dfs1(int x){
	// cout<<x<<" ";
	int sum=0,ans=0;
	for(int i=head1[x];i;i=a1[i].nxt){
		int v=a1[i].to;
		sum+=dfs1(v);
		// cout<<v<<endl;
	}
	if(b[x])ans=minn[x];
	else ans=min(sum,minn[x]);
	b[x]=0,head1[x]=0;
	I_love_Furina ans;
}
signed main(){
	IOS;//FIO("");
	cin>>n;
	for(int i=1,u,v,w;i<n;i++)cin>>u>>v>>w,add(u,v,w),add(v,u,w);
	minn[1]=inf;
	dfs(1,0);
	cin>>m;
	while(m--){
		int k;
		cin>>k;
		for(int i=1;i<=k;i++)cin>>q[k],b[q[k]]=1;
		sort(q+1,q+k+1,cmp);
		int len=0;
		num1=0;
		t[++len]=1;
		for(int i=1;i<k;i++)t[++len]=q[i],t[++len]=lca(q[i],q[i+1]);
		t[++len]=q[k];
		sort(t+1,t+len+1,cmp);
		len=unique(t+1,t+len+1)-t-1;
		for(int i=1;i<len;i++)add1(lca(t[i],t[i+1]),t[i+1],0);//,cout<<lca(t[i],t[i+1])<<" "<<t[i+1];
		cout<<dfs1(1)<<endl;
	}
	
	I_love_Furina forever;
}
2024/8/13 10:31
加载中...