A一个,WA一个,其他全M,求助!
查看原帖
A一个,WA一个,其他全M,求助!
561907
Furina_Saikou楼主2023/10/29 10:41
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+1;
int n,m,k,cnt,head[N],to[N],ne[N],w[N],id,dfn[N],a[N],dep[N],fa[N][21],st[N][20];
inline void add(int x,int y,int z)
{
	to[++id]=y,w[id]=z,ne[id]=head[x],head[x]=id;
}
inline void dfs(int u,int f)
{
	dfn[u]=++cnt;
	fa[u][0]=f;
	dep[u]=dep[f]+1;
	for(int i=1;i<20;i++)
	{
		fa[u][i]=fa[fa[u][i-1]][i-1];
		st[u][i]=min(st[u][i-1],st[fa[u][i-1]][i-1]);
	}
	for(int i=head[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==f)continue;
		st[v][0]=w[i];
		dfs(v,u);
	}
}
inline bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
inline int lca(int x, int y)
{
	if(dep[x]<dep[y])
	{
		swap(x,y);
	}
	for(int i=19;i>=0;i--)
	{
		if(dep[fa[x][i]]>=dep[y])
		{
			x=fa[x][i];
		}
	}
	if(x==y)
	{
		return x;
	}
	for(int i=19;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}
int len,head2[N],to2[N],w2[N],ne2[N],tr[N],id2;
bool vis[N];
inline void add2(int x,int y,int z)
{
	to2[++id2]=y,w2[id2]=z,ne2[id2]=head2[x],head2[x]=id2;
}
inline int find(int x,int y)
{
	int minn=2147483647;
	for(int i=19;i>=0;i--)
	{
		if(dep[x]<=dep[y])
		{
			minn=min(minn,st[y][i]);
			y=fa[y][i];
		}
	}
	return minn;
}
inline void build_tree()
{
	sort(a+1,a+k+1,cmp);
	a[0]=1;
	len=0;
	for(int i=1;i<=k;i++)
	{
		tr[++len]=lca(a[i-1],a[i]);
		tr[++len]=a[i];
	}
	sort(tr+1,tr+len+1,cmp);
	len=unique(tr+1,tr+len+1)-tr-1;
	for(int i=2;i<=len;i++)
	{
		int r=lca(tr[i-1],tr[i]);
		if(vis[r]&&r!=1)continue;
		int x=find(r,tr[i]);
		add2(r,tr[i],x);
		add2(tr[i],r,x);
	}	
}
int dp[N];
inline void dfs_dp(int u,int value)
{
	dp[u]=value;
	if(vis[u])
	{
		return;
	}
	int sum=0;
	for(int i=head2[u];i;i=ne2[i])
	{
		int v=to2[i];
		if(v==fa[u][0])continue;
		dfs_dp(v,w2[i]);
		sum+=dp[v];
	}
	if(sum)
	{
		dp[u]=min(dp[u],sum);
	}
}
signed main()
{
	memset(st,0x7f,sizeof st);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	dfs(1,0);
	cin>>m; 
	while(m--)
	{
		memset(head2,0,sizeof head2);
		memset(dp,0,sizeof dp);
		memset(vis,0,sizeof vis);
		id2=0;
		cin>>k;
		for(int i=1;i<=k;i++)
		{
			cin>>a[i];
			vis[a[i]]=1;
		}
		build_tree();
		dfs_dp(1,2147483647);
		cout<<dp[1]<<"\n";
	}
	return 0;
}
2023/10/29 10:41
加载中...