第一个点MLE!!!(求助dalao看看)
查看原帖
第一个点MLE!!!(求助dalao看看)
360279
ytcfghyeee楼主2023/11/13 11:43
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar
#define pf printf
#define LLINF 0x3f3f3f3f3f3f3f3f 
int re(){
	int s=0,a=0;
	char f=gc();
	while(f<'0'||f>'9'){
		a|=(f=='-');
		f=gc();
	}
	while('0'<=f&&f<='9'){
		s=s*10 +f-'0';
		f=gc();
	} return a?-s:s;
}

#define N 500050
int n,m;
int fir[N],tot;
struct xy{
	int v;
	long long w;
	int nt;
}e[N<<1];
int fa[N][22],dp[N];
long long ds[N];
int dn[N],ti;
int lh[N];
int q[N];
int sk[N],sl,ql;
bool fl[N];

void addl(int u,int v,int w){
	e[++tot]=(xy){
		v,w,fir[u]
	};fir[u]=tot;
}

#define vt e[i].v
#define mn(a,b) ((a)<(b)?(a):(b))
#define mx(a,b) ((a)>(b)?(a):(b))
void dfs(int u,int pre){
	int i,k;
	fa[u][0]=pre;
	dn[u]=++ti;
	for(i=fir[u];i;i=e[i].nt)
	if(vt!=pre&&!dn[vt]){
		ds[vt]=mn(ds[u],e[i].w);
		dp[vt]=dp[u]+1;
		dfs(vt,u);
	}
	for(k=1;k<=lh[dp[u]];++k){
		fa[u][k]=fa[fa[u][k-1]][k-1];
	}
}
inline int lca(int x,int y){
	if(dp[y]>dp[x])swap(x,y);
	int nl=dp[x]-dp[y],i=0;
	while(nl){
		if(nl&1)x=fa[x][i];
		++i;nl>>=1;
	}
	while(x!=y){
		i=0;
		while(fa[x][i+1]!=fa[y][i+1])++i;
		x=fa[x][i];y=fa[y][i];
	}return x;
}
inline bool cmp(int x,int y){return dn[x]<dn[y];}
inline long long work(int u){
//	if(fl[u]==1) return LLINF;
	int i;
	long long s=0;
	for(i=fir[u];i;i=e[i].nt){
		long long n1=work(vt);
		s+=n1;
	}
	s=mn(s,ds[u]);
	if(fl[u]) s=ds[u];
	fir[u]=0;
	fl[u]=0;
	return s;
}
signed main(){
	register int i,j;
	int x,y,z,k;
	n=re();
	for(i=1;i<n;++i){
		x=re();
		y=re();
		z=re();
		addl(x,y,z);
		addl(y,x,z);
		lh[i+1]=lh[(i+1)>>1]+1;
	}
	ds[1]=LLINF;
	dfs(1,0);
	m=re();
	for(i=1;i<=n;++i)
		fir[i]=0,fl[i]=0;
	while(m--){
		k=re();ql=0;tot=0;
		
		for(i=1;i<=k;++i){
			q[i]=re();fl[q[i]]=1;
		}sort(q+1,q+k+1,cmp);
		sk[sl=1]=1;
		for(i=1;i<=k;++i){
			int now=q[i];
			int lc=lca(now,sk[sl]);
			while (1)
				if (dp[lc]>=dp[sk[sl-1]])
				{
					if (lc!=sk[sl]) 
					{
						addl(lc,sk[sl],0);
						if (lc!=sk[sl-1])  
							sk[sl]=lc;
						else 
							sl--;
					}
					break;
				}
				else 
				{
					addl(sk[sl-1],sk[sl],0);  
					sl--;
				}
			sk[++sl]=now;
		}
		for(i=1;i<sl;++i)
		addl(sk[i],sk[i+1],0);
		
		pf("%lld\n",work(1));
		
		
	}
	return 0;
}
2023/11/13 11:43
加载中...