求助
  • 板块灌水区
  • 楼主LonelyPatient
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/22 10:09
  • 上次更新2023/10/22 10:42:09
查看原帖
求助
1158060
LonelyPatient楼主2023/10/22 10:09
#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>

#define ll long long

const int MXN=1e5+10;

std::vector<ll> v[MXN];
std::vector<ll> w[MXN];

ll n,m,t,i,j;

ll dp[MXN],f[MXN];

void dfs(ll cur,ll father)
{
	ll sz=v[cur].size();
	
	ll ans=0;
	
	for(i=0;i<sz;++i)
	{
		ll nxt=v[cur][i];
		
		if(nxt==father)
			continue;			
			
		if(f[nxt])
		{
			ans+=w[cur][i];			
			continue;
		}
		
		dp[nxt]=std::min(dp[cur],w[cur][i]);
		
		dfs(nxt,cur);
		
		ans+=dp[nxt];
	}
	
	dp[cur]=std::min(dp[cur],ans);
}

int main()
{
	std::cin>>n;
	
	for(i=1;i<n;++i)	
	{
		ll x,y,z;
		
		std::cin>>x>>y>>z;
		
		v[x].push_back(y);
		v[y].push_back(x);
		
		w[x].push_back(z);
		w[y].push_back(z);
	}
	
	std::cin>>t;
	
	while(t--)
	{
		memset(f,0,sizeof f);
		
		std::cin>>m;
		
		dp[1]=0x7fffff;
		
		for(i=1;i<=m;++i)
		{
			ll x;
			
			std::cin>>x;			
			
			f[x]=1;
		}

		dfs(1,0);
		
		std::cout<<dp[1]<<'\n';
	}
	return 0;
}
//f[cur]!=0 -> dp[i]=dp[i]+w(i,cur)
//f[cur]==0 -> dp[i]=dp[i]+min(dp[u]+w(i,cur))

为什么会死递归

2023/10/22 10:09
加载中...