MLE 不知空间大小,求助
查看原帖
MLE 不知空间大小,求助
1268457
20090818Cc楼主2025/6/27 21:36

谢谢啦~

#include<bits/stdc++.h>
#define int long long
using namespace std;
//取宏定义 
const int INF=0x7ffff;
const int M=2e5+5e4+110;
//快读 
inline int read(){
	int sum=0,k=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')k=-1;c=getchar();
	}while(c>='0'&&c<='9'){sum=sum*10+c-48; c=getchar();
	}return sum*k;
}
//原图的链式前向星 
int Head[M],Tot=0;
struct Line_Node{
	int Next,To,Val;
}Ed[M<<2];
inline void Adde(int u,int v,int w){
	Ed[++Tot]={Head[u],v,w};
	Head[u]=Tot;
}
//树剖预处理结点权值与LCA 
int va[M];
int Fa[M],Siz[M],Son[M],Deep[M];
//第一遍dfs 
inline void dfs1(int u,int fa){
	Fa[u]=fa;Siz[u]=1;//记录父亲与子树大小 
	Deep[u]=Deep[fa]+1;//记录深度 
	for(int i=Head[u];i;i=Ed[i].Next){
		int v=Ed[i].To;
		if(v==fa) continue;
		va[v]=min(va[u],Ed[i].Val);//结点权值 
		dfs1(v,u);
		if(Siz[v]>Siz[Son[u]]) Son[u]=v;//重儿子 
		Siz[u]+=Siz[v];
	}
}
//第二次dfs 
int Tim=0;
int Id[M],Top[M];
inline void dfs2(int u,int topf){
	Id[u]=++Tim;Top[u]=topf;//dfs序 
	if(!Son[u]) return ;
	dfs2(Son[u],topf);
	for(int i=Head[u];i;i=Ed[i].Next){
		int v=Ed[i].To;
		if(v==Fa[u]) continue;
		if(v==Son[u]) continue;
		dfs2(v,v);//向下搜 
	}
}//处理LCA 对了版子 
inline int Get_LCA(int a,int b){
	while(Top[a]!=Top[b]){
		if(Deep[Top[a]]<Deep[Top[b]]) swap(a,b); 
		a=Fa[Top[a]];
	}if(Deep[a]<Deep[b]) swap(a,b);
	return b;
}
//struct virtual_tree{
//	int Next,To;
//}Ved[M];
//int Vhead[M],Vtot=0;
//inline void Vadde(int u,int v){
//	Ved[++Vtot]={Vhead[u],v};
//	Vhead[u]=Vtot;
//}
vector<int>e[M];//虚树边 
inline void Vadde(int u,int v){
	e[u].push_back(v);
}
int top=0;//手写栈 
int Sta[M];
inline void Insert(int u){//插入 
	if(top==1){Sta[++top]=u;return ;}//栈中只有一个结点 
	int lca=Get_LCA(u,Sta[top]);//搞个LCA 
	if(lca==Sta[top]) return ;
	while(top>1&&Id[Sta[top-1]>=Id[lca]])
		Vadde(Sta[top-1],Sta[top]),top--;
	if(lca!=Sta[top]) Vadde(lca,Sta[top]),Sta[top]=lca;
	Sta[++top]=u;
}
inline int Get_Dp(int u){
	if(e[u].size()==0) return va[u];//本来就是空的 
	int sum=0;//累加 
	for(auto v:e[u])
		sum+=Get_Dp(v);
	e[u].clear();//清空 
	return min(sum,va[u]);//dp嘛 
}
int a[M];//存关键点 
inline bool cmp(const int &a,const int &b){
	return Id[a]<Id[b];//按照dfs序排 
}
signed main(){
	int n=read();va[1]=INF; 
	for(int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		Adde(u,v,w);Adde(v,u,w);
	}
	
	dfs1(1,0);dfs2(1,1);
	int m=read();
	while(m--){
		int k=read();
		for(int i=1;i<=k;i++) a[i]=read();
		sort(a+1,a+1+k,cmp);
		Sta[top=1]=1;
//		cout<<'\n';
//		for(int i=1;i<=k;i++) cout<<"   "<<a[i]<<"   ";
//		cout<<'\n';
		for(int i=1;i<=k;i++) Insert(a[i]);
		while(top>0) Vadde(Sta[top-1],Sta[top]),top--;
		printf("%lld\n",Get_Dp(1));
	}
	return 0;
}
/*
10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6
*/
2025/6/27 21:36
加载中...