TLE60分 玄关
查看原帖
TLE60分 玄关
748015
Yang_YL楼主2025/6/28 18:06
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,nn,m,a[N],b[N],oil[N],f[N][30],f1[N][30],dpf[N],dfn[N],cnt;long long dp[N];
struct Edge{int y,z;};
vector<Edge> v[N],V[N];
int st[N],cnt1;
void pdfs(int k,int fa){
	dfn[k]=++cnt;dpf[k]=dpf[fa]+1;
	for(int i=0;i<v[k].size();i++) if(v[k][i].y!=fa) f1[v[k][i].y][0]=v[k][i].z,pdfs(v[k][i].y,k);
	f[k][0]=fa;
}
int lca(int x,int y){
	if(dpf[x]<dpf[y]) swap(x,y);
	for(int i=19;i>=0;i--) if(dpf[f[x][i]]>=dpf[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
int so(int x,int y){
    // cout<<x<<" "<<y<<" ";
	if(dpf[x]<dpf[y]) swap(x,y);
	int ans=1e9;
	for(int i=19;i>=0;i--) if(dpf[f[x][i]]>=dpf[y]) ans=min(ans,f1[x][i]),x=f[x][i];
    // cout<<ans<<endl;
	return ans;
}
void dfs(int k,int fa){
//	cout<<k<<" "<<fa<<endl;
	if(oil[k]){
		int Lca=lca(k,st[cnt1]);
		while(cnt1&&dfn[st[cnt1]]>dfn[Lca]){
			int x=st[cnt1];cnt1--;
            if(dfn[st[cnt1]]<dfn[Lca]){b[++nn]=Lca,st[++cnt1]=Lca;}
			V[st[cnt1]].push_back(Edge{x,so(st[cnt1],x)});
		}
        if(cnt1&&st[cnt1]!=k){b[++nn]=k,st[++cnt1]=k;}
	}
	for(int i=0;i<v[k].size();i++) if(v[k][i].y!=fa) dfs(v[k][i].y,k);
}
void Dp(int k){
	if(oil[k]){dp[k]=1e18;return;}
	for(int i=0;i<V[k].size();i++){
		Dp(V[k][i].y);
		dp[k]+=min(dp[V[k][i].y],1ll*V[k][i].z);
	}
    // cout<<k<<" "<<dp[k]<<endl;
}
signed main(){
	scanf("%d",&n);
	for(int i=1,x,y,z;i<n;i++) scanf("%d%d%d",&x,&y,&z),v[x].push_back(Edge{y,z}),v[y].push_back(Edge{x,z});
	pdfs(1,0);int T;scanf("%d",&T);
    for(int i=1;i<20;i++)
	for(int k=1;k<=n;k++){
		f[k][i]=f[f[k][i-1]][i-1];		
		f1[k][i]=min(f1[k][i-1],f1[f[k][i-1]][i-1]);
        // cout<<"f1:"<<k<<" "<<i<<" "<<f1[k][i]<<endl;
	}
	while(T--){
 		for(int i=1;i<=nn;i++){V[b[i]].clear();dp[b[i]]=0;oil[b[i]]=0;}nn=1;b[1]=1;       
		scanf("%d",&m);for(int i=1;i<=m;i++) scanf("%d",&a[i]),oil[a[i]]=1;
		st[cnt1=1]=1;dfs(1,0);while(cnt1>1){int x=st[cnt1];cnt1--;V[st[cnt1]].push_back(Edge{x,so(st[cnt1],x)});}
		Dp(1);printf("%lld\n",dp[1]);
	}
	return 0;
}

TLE on test 5,6,7,9 QAQ

2025/6/28 18:06
加载中...