50分求调WA
查看原帖
50分求调WA
701387
xiaoliebao1115楼主2024/5/8 19:10
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=25*1e4+10;
ll n,cnt,cnt2,num;
struct node
{
	ll u,v,w;
}edge[2*maxn];
struct student
{
	ll u,v,w;
}edge2[2*maxn];
ll head[maxn],nxt[2*maxn],c[maxn],dp[maxn],head2[maxn],nxt2[maxn],steps[maxn];
ll dfn[maxn],a[maxn];
int dp2[maxn][21],dp3[maxn][21];
bool is[maxn];
void add2(ll u,ll v,ll w)
{
	cnt2++;
	edge2[cnt2].u=u;
	edge2[cnt2].v=v;
	edge2[cnt2].w=w;
	nxt2[cnt2]=head2[u];
	head2[u]=cnt2;
}
void add(ll u,ll v,ll w)
{
	cnt++;
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void dfs(ll u,ll fa)
{
	if(is[u])
	{
		dp[u]=1e15;
		return ;
	}
	for(ll i=head[u];i;i=nxt[i])
	{
		ll v=edge[i].v;
		if(v!=fa)
		{
			ll w=edge[i].w;
			dfs(v,u);
			dp[u]+=min(w,dp[v]);
		//	cout<<v<<" "<<dp[v]<<" "<<w<<endl;
		}
	}
//	cout<<u<<" "<<fa<<" "<<dp[u]<<endl;
	return ;
}
void dfs2(ll u,ll fa)
{
	num++;
	dfn[u]=num;
	for(int i=head2[u];i;i=nxt2[i])
	{
		ll v=edge2[i].v;
		if(v!=fa) dfs2(v,u);
	}
}
bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
void dfs3(int u,int fa,int w)
{
	dp2[u][0]=fa;
	dp3[u][0]=w;
	steps[u]=steps[fa]+1;
	for(int i=1;i<=20;i++)
	{
		dp2[u][i]=dp2[dp2[u][i-1]][i-1];
		if(dp2[u][i]==0) break;
	}
	for(int i=1;i<=20;i++)
	{
		if(dp2[u][i]==0) break;
		dp3[u][i]=min(dp3[u][i-1],dp3[dp2[u][i-1]][i-1]);
	}
	for(int i=head2[u];i;i=nxt2[i])
	{
		int v=edge2[i].v;
		if(v!=fa) dfs3(v,u,edge2[i].w);
	}
}
int lca(int a,int b) 
{
	if(steps[a]<steps[b]) swap(a,b);
	for(int i=20;i>=0;i--)
	{
		int to=dp2[a][i];
		if(to!=0&&steps[to]>=steps[b]) a=to;
	}
	if(a==b) return a;
	for(int i=20;i>=0;i--)
	{
		if(dp2[a][i]!=dp2[b][i]) a=dp2[a][i],b=dp2[b][i];
	}
	return dp2[a][0];
}
int query(int gf,int son)
{
	int a=son,ans=INT_MAX;
	for(int i=20;i>=0;i--)
	{
	//	cout<<dp2[a][i]<<endl;
		if(steps[dp2[a][i]]>=steps[gf]) 
		{
			ans=min(ans,dp3[a][i]);
			a=dp2[a][i];
		//	cout<<dp3[a][i]<<endl;
		}
	}
	return ans;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		ll x,y,w;
		scanf("%lld%lld%lld",&x,&y,&w);
		add2(x,y,w);
		add2(y,x,w);
	} 
	dfs2(1,0);
	dfs3(1,0,0);
	ll q;
	cin>>q;
	while(q--)
	{
		ll k;
		scanf("%lld",&k);
		for(int i=1;i<=k;i++)
		{
			scanf("%lld",&c[i]);
			is[c[i]]=1;
		}
		sort(c+1,c+k+1,cmp);
		int len=0;
		for(int i=1;i<k;i++)
		{
			a[++len]=c[i];
			a[++len]=lca(c[i],c[i+1]);
		}
		a[++len]=c[k];
		sort(a+1,a+len+1,cmp);
	//	for(int i=1;i<=len;i++) cout<<a[i]<<" ";
	//	cout<<endl;
		len=unique(a+1,a+len+1)-a-1;
		
	//	for(int i=1;i<=len;i++) cout<<a[i]<<" ";
	//	cout<<endl;
		for(int i=1,lc;i<len;i++)
		{
			lc=lca(a[i],a[i+1]);
			int y=query(lc,a[i+1]);
			add(lc,a[i+1],y);
			add(a[i+1],lc,y);
		//	cout<<lc<<" "<<a[i+1]<<" "<<y<<endl;
		}
	//	cout<<endl;
		if(a[1]!=1) 
		{
			int y=query(1,a[1]);
			add(1,a[1],y),add(a[1],1,y);
			a[++len]=1;
		}
		dfs(1,0);
		printf("%lld\n",dp[1]);
		//	for(int i=1;i<=n;i++) cout<<head[i]<<" ";
	//	cout<<endl;
		for(int i=1;i<=len;i++) 
		{
		//	cout<<head[a[i]]<<" ";
			for(int i=head[a[i]];i;) 
			{
				int bf=i;
				i=nxt[i],nxt[bf]=0;
			//	cout<<bf<<"****";
			}
			head[a[i]]=0;dp[a[i]]=0;
		}
	//	cout<<endl;
	//	for(int i=1;i<=n;i++) cout<<head[i]<<" ";
	//	cout<<endl;
	//	for(int i=1;i<=cnt;i++) cout<<nxt[i]<<" ";
	//	dp[1]=0;
		for(int i=1;i<=k;i++) is[c[i]]=0;
		cnt=0;
	}
	return 0;
}
2024/5/8 19:10
加载中...