3 条题解
-
0
/************************************ Note Book: ************************************/ #include <iostream> #include <cstdio> #include <iomanip> #include <cmath> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <map> #include <queue> #include <math.h> #define LL long long using namespace std; const int INF = 0x3f3f3f3f; const int N = 1e5 + 10; int n ; vector<int > p[N]; int num[N]; bool vis[N]; int dp[N][3]; void dfs(int id , int fa) { int d = INF; for(int i = 0; i < p[id].size(); i++) { int son = p[id][i]; if(son == fa) { continue; } dfs(son , id); dp[id][0] += min(dp[son][1] , dp[son][2]); dp[id][1] += min(dp[son][2] , min(dp[son][1] , dp[son][0])); dp[id][2] += min(dp[son][2] , dp[son][1]); d = min(d , dp[son][1] - min(dp[son][2] , dp[son][1])); } dp[id][2] += d; dp[id][1] += num[id]; } int main() { cin >> n ; for(int i = 0; i < n ; i++) { int id; cin >> id; cin >> num[id]; int t; cin >> t; while( t-- ) { int x; cin >> x; p[id].push_back(x); p[x].push_back(id); } } int root = 0; for(int i = 1; !root && i <= n; i++) { if(!vis[i]) { root = i; } } dfs(root , -1); cout << min(dp[root][2] , dp[root][1]) << endl; return 0; }
信息
- ID
- 474
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 151
- 已通过
- 43
- 上传者