萌新求助,刚学OI1e-9s
查看原帖
萌新求助,刚学OI1e-9s
142068
QAQQWQ楼主2021/10/10 00:52

#7TLE了,树用vector存的QAQ

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
int n,m;
std::vector<pair<int ,long long > >tree[250009];
vector<int > xt[250009]; 
long long tof[250009],fs[250009];
int f[250009][23],id[250009],top=0,h[250009];
bool qwq[250009];
int z[250009],tot=0,dep[250009];
inline int read(){
	int sum=0,fh=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')fh=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum*=10;
		sum+=c-'0';
		c=getchar();
	}
	return sum*fh;
}
void dfs(int now){
	dep[now]=dep[f[now][0]]+1;
//	cout<<"dfs:"<<now<<endl;
	for(int i=1;i<=21;i++){
		f[now][i]=f[f[now][i-1]][i-1];
//		cout<<"f:"<<now<<" "<<i<<" "<<f[now][i]<<endl;
	}
	top++;
	id[now]=top;
	int sn=tree[now].size();
	for(int i=0;i<sn;i++){
		int v=tree[now][i].first;
		long long w=tree[now][i].second;
		if(v!=f[now][0]){
			f[v][0]=now;
			dfs(v);
		}
		else{
			tof[now]=w;
		}
	}
	return ;
} 
bool cmp(int a,int b){
	return id[a]<id[b];
}
int lca(int a,int b){
	if(dep[a]>dep[b])swap(a,b);
	for(int i=21;i>=0;i--){
		if(dep[f[b][i]]>=dep[a]){
			b=f[b][i];
		}
	}
	if(a==b)return a;
//	cout<<a<<" "<<b<<" "<<f[a][0]<<endl;
	for(int i=21;i>=0;i--){
		if(f[b][i]!=f[a][i]){
			a=f[a][i];
			b=f[b][i];
		}
	}
	return f[a][0];
}
void findf(int now,int tofind){
	if(now==tofind)return ;
	xt[now].clear();
	findf(f[now][0],tofind);
	tot++;
	z[tot]=now;
	qwq[now]=false;
	xt[f[now][0]].pb(now);
//	cout<<"build:"<<now<<" "<<f[now][0]<<" "<<tofind<<endl;
	return ;
}
void build(int kn){
	tot=1;
	z[1]=1;
	xt[1].clear();
	for(int i=1;i<=kn;i++){
		xt[h[i]].clear();
		int lcas=lca(z[tot],h[i]);
//		cout<<"lca:"<<z[tot]<<" "<<h[i]<<" "<<lcas<<endl;
		while(z[tot]!=lcas&&tot){
			tot--;
		}
		findf(h[i],z[tot]);
		qwq[h[i]]=true;
	}
	return ;
} 
void dp(int now){
//	cout<<"now:"<<now<<" "<<xt[now].size()<<" "<<f[now][0]<<" "<<tof[now]<<" "<<qwq[now]<<endl;
	if(qwq[now]){
		fs[now]=tof[now];
//		cout<<fs[now]<<endl;
		return ;
	}
	fs[now]=0;
	int sn=xt[now].size();
	for(int i=0;i<sn;i++){
		int v=xt[now][i];
		long long w=tof[v];
		if(v!=f[now][0]){
			dp(v);
			fs[now]+=min(fs[v],w);
		}
	}
//	cout<<fs[now]<<endl;
	return ;
}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		tree[u].pb(mp(v,w));
		tree[v].pb(mp(u,w));
	}
	dfs(1);
	m=read();
	while(m--){
		int kn=read();
		for(int i=1;i<=kn;i++){
			h[i]=read();
		} 
		sort(h+1,h+kn+1,cmp);
		build(kn);
		dp(1);
		cout<<fs[1]<<endl;
	} 
//	  fclose(stdin);
//    fclose(stdout);
	return 0;
}

2021/10/10 00:52
加载中...