树形dp20pts求助
查看原帖
树形dp20pts求助
1183074
xzy_AK_IOI楼主2024/11/24 11:05
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const ll inf=1e12;
#define F(i,k,n) for (int i=k;i<=n;i++)
int n,root,a,b,c;
struct edge{
	int to;
	int w;
};
struct node{
	vector <edge> son;
	int Size;
}tree[N]; 
ll dp[N];
void dfs(int p,ll last){
	if (!tree[p].Size){
		dp[p]=last;
		return ;
	}
	ll cnt=0;
	F(i,0,tree[p].Size-1){
		int j=tree[p].son[i].to;
		int y=tree[p].son[i].w;
		dfs(j,y);
		cnt+=dp[j];
	}
	dp[p]=min(cnt,last);
}
int main(){ 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>root;
	F(i,1,n-1){
		cin>>a>>b>>c;
		tree[a].son.push_back((edge){b,c});
		tree[a].Size++;
	}
	dfs(root,inf);
	cout<<dp[root];
	return 0;
}
2024/11/24 11:05
加载中...