悬关求助
  • 板块学术版
  • 楼主lovelish
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/20 20:37
  • 上次更新2024/6/20 20:45:40
查看原帖
悬关求助
760954
lovelish楼主2024/6/20 20:37

谁能帮我看一下这代码怎么就RE了(去掉注释)(树形dp)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<int> a[200010];
vector<int> b[200010];
int l[200010];
int dp[200010];
int ans=0;
void dfs(int v,int syg)//syg指上一个
{
	for(int i=0;i<l[v];i++)
	{
		if(a[v][i]!=syg)if(dp[a[v][i]]==-1)dfs(a[v][i],v);
	}
	dp[v]=0;
	for(int i=0;i<l[v];i++)
	{
		if(a[v][i]!=syg)dp[v]+=min(b[v][i],dp[a[v][i]]);
	}
	if(dp[v]==0)dp[v]=1e9;
	if(syg==0)ans=dp[v];
}
//void dfs2(int v,int minn,int syg)
//{
//	for(int i=0;i<l[v];i++)
//	{
//		if(a[v][i]!=syg)
//		{
//			int x=dp[v]-min(dp[a[v][i]],b[v][i]);
//			x=min(x,b[v][i]);
//			int y=dp[a[v][i]]==1e9? 0:dp[a[v][i]];
//			if(x+y>ans)ans=x+dp[a[v][i]];
//			dfs2(a[v][i],x+y,v);
//		}
//		
//	}
//}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n-1;i++)
		{
			dp[i]=-1;
			int x,y,z;
			cin>>x>>y>>z;
			a[x].push_back(y);
			b[x].push_back(z);
			a[y].push_back(x);
			b[y].push_back(z);
			l[x]++;l[y]++;
		}
//		for(int i=1;i<=n;i++)
//		{
//			for(int j=0;j<l[i];j++)
//			{
//				cout<<b[i][j]<<" ";
//			 } 
//			 cout<<endl;
//		}
		dp[n]=-1;
		dfs(1,0);
		//dfs2(1,1e9,0);
//		for(int i=1;i<=n;i++)
//		{
//			cout<<dp[i]<<" ";
//		}
//		cout<<endl;
		cout<<ans<<endl;
	}
	return 0;
}

2024/6/20 20:37
加载中...