为什么会 MLE
查看原帖
为什么会 MLE
224111
zysqh楼主2020/8/9 16:18
#include <cstdio>
#include <iostream>
#include <algorithm>
#define S 251234
using namespace std;
int sta[S],top;
int h[S*2],cnt;
struct mmmm{
	int ne,to,val;
}e[S*2];
void add(int u,int v,int val){
	e[++cnt].ne=h[u];
	e[cnt].to=v;
	e[cnt].val=val;
	h[u]=cnt;
}
struct mmm{
	int ne,to;
}e1[S];
int h1[S],cnt1;
void add1(int u,int v){
	e1[++cnt1].ne=h1[u];
	e1[cnt1].to=v;
	h1[u]=cnt1;
}
int dep[S],dfn[S];
int tot;
int sz[S],son[S];
int up[S];int ff[S];
void dfs(int u,int fa){
	dfn[u]=++tot;
	sz[u]=1;ff[u]=fa;
	for(int i=h[u];i;i=e[i].ne){
		int v=e[i].to;
		if(v==fa)continue;
		up[v]=min(up[u],e[i].val);
		sz[u]+=sz[v];
		dep[v]=dep[u]+e[i].val;
		if(sz[v]>sz[son[u]])son[u]=v;
		dfs(v,u);
	}
}

int topfront[S];
void shudfs1(int u,int tv){
	topfront[u]=tv;
	
	if(son[u])shudfs1(son[u],tv);
	for(int i=h[u];i;i=e[i].ne){
		int v=e[i].to;
		if(v==ff[u]||v==son[u])continue;
		shudfs1(v,v);
	}
}

int LCA(int x,int y){
	while(dep[x]!=dep[y]){
		if(dep[x]<=dep[y])swap(x,y);
		x=ff[topfront[x]];
	}
	return dep[x]<dep[y]?x:y;
}
int a[S];
bool cmp(int &a,int &b){
	return dfn[a]<dfn[b];
}
void buil(int x){
	if(top==0){
		sta[++top]=x;
		return;
	}
	int lca=LCA(sta[top],x);
	while(dep[sta[top-1]]>dep[lca]){
		lca=LCA(sta[top],x);
		add1(sta[top],sta[top-1]);
		top--;
	}
	int u=sta[top];
	int v=x;
	int fa=sta[top-1];
	lca=LCA(sta[top],x);
	if(dep[lca]>dep[fa]&&dep[lca]<dep[u]){
		add1(lca,u);
		top--;
		sta[++top]=lca;
	}
	if(lca==fa){
		add1(fa,u);
		top--;
	}
	sta[++top]=v;
}
int valuea[S];
int f[S];
void dp(int u){
	int now=0;
	for(int i=h1[u];i;i=e1[i].ne){
		int v=e1[i].to;
		f[v]=up[v];
		dp(v);
		now+=f[v];
	}
	if(!valuea[u])f[u]=min(now,f[u]);
	valuea[u]=0;
	h1[u]=0;
}
int n;
int m;
int xx,yy,zz;
signed main(){
	scanf("%d",&n);
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&xx,&yy,&zz);
		add(xx,yy,zz);
		add(yy,xx,zz);
	}
	dep[1]=1;
	up[1]=0x3f3f3f;
	dfs(1,0);
	shudfs1(1,1);
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		scanf("%d",&xx);
		f[1]=0x3f3f3f;
		a[1]=1;
		for(int i=2;i<=xx+1;++i){
			scanf("%d",&a[i]);
			valuea[a[i]]=1;
		}
		sort(a+1,a+2+xx,cmp);

		top=0;
		cnt1=0;
		for(int i=1;i<=xx+1;++i){
			buil(a[i]);
		}
		while(top>0){
			top--;
			add1(sta[top],sta[top+1]);
		}
		valuea[1]=0;
		dp(1);
		printf("%d\n",f[1]);
	}
} 
2020/8/9 16:18
加载中...