3 条题解

  • 0
    @ 2024-3-24 16:38:30
    /************************************
    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
    上传者