题目描述

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。 皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状，某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。 可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。 帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

数据范围：对于 100% 的数据，0<n≤1500。

我的Code：

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize ("Ofast")
using namespace std;
int n,i,x,v,m,dp[1510][3],w[1510];vector<int> f[1510];
void dfs(int x,int fx){
	dp[x][1]=w[x];int small=2e9;
	for(int i=0;i<f[x].size();i++){
		int sx=f[x][i];
		if(sx==fx) continue;
		dfs(sx,x);
		dp[x][0]+=min(dp[sx][1],dp[sx][2]);
		dp[x][1]+=min(dp[sx][0],min(dp[sx][1],dp[sx][2]));
		dp[x][2]+=min(dp[sx][1],dp[sx][2]);
		small=min(small,dp[sx][1]-min(dp[sx][1],dp[sx][2])); 
	}
	dp[x][2]+=small;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>x;cin>>w[x]>>m;
		while(m--) cin>>v,f[x].push_back(v),f[v].push_back(x);
	}
	dfs(1,0);
	cout<<min(dp[1][0],min(dp[1][1],dp[1][2]));
	return 0;
}

这道站外题，大佬救我！