7 条题解

  • 9
    @ 2023-8-9 10:27:47
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e4+10;
    const int INF=0x3f3f3f3f;
    int dp[N][3],n,u,v,n1;
    vector<int>vc[N];
    void dfs(int u,int fa){
    	bool flag=0;
    	int minn=INF;
    	for(int i=0;i<vc[u].size();i++){
    		int v=vc[u][i];
    		if(v==fa)continue;
    		dfs(v,u);
    		dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
    		dp[u][2]+=min(dp[v][0],dp[v][1]);
    		dp[u][1]+=min(dp[v][0],dp[v][1]);
    		minn=min(minn,dp[v][0]-min(dp[v][0],dp[v][1]));
    	}
    	dp[u][1]+=minn;
    }
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>u;
    		cin>>dp[u][0];
    		cin>>n1;
    		for(int j=1;j<=n1;j++){
    			cin>>v;
    			vc[u].push_back(v);
    			vc[v].push_back(u);
    		}
    	}
    	dfs(1,0);
    	cout<<min(dp[1][0],dp[1][1]);
    }
    
    • 1
      @ 2025-7-15 15:10:18

      #include<bits/stdc++.h> using namespace std; const int N=1e4+10; const int INF=0x3f3f3f3f; int dp[N][3],n,u,v,n1; vectorvc[N]; void dfs(int u,int fa){ bool flag=0; int minn=INF; for(int i=0;i<vc[u].size();i++){ int v=vc[u][i]; if(v==fa)continue; dfs(v,u); dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2])); dp[u][2]+=min(dp[v][0],dp[v][1]); dp[u][1]+=min(dp[v][0],dp[v][1]); minn=min(minn,dp[v][0]-min(dp[v][0],dp[v][1])); } dp[u][1]+=minn; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>u; cin>>dp[u][0]; cin>>n1; for(int j=1;j<=n1;j++){ cin>>v; vc[u].push_back(v); vc[v].push_back(u); } } dfs(1,0); cout<<min(dp[1][0],dp[1][1]); }

      • 0
        @ 2025-7-25 10:19:03
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include<bits/stdc++.h> 
        using namespace std; 
        const int N=1e4+10; 
        const int INF=0x3f3f3f3f; 
        int dp[N][3],n,u,v,n1; 
        vectorvc[N]; 
        void dfs(int u,int fa){ 
        	bool flag=0; 
        	int minn=INF; 
        	for(int i=0;i<vc[u].size();i++){ 
        		int v=vc[u][i]; 
        		if(v==fa)continue; 
        		dfs(v,u); 
        		dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2])); 
        		dp[u][2]+=min(dp[v][0],dp[v][1]); 
        		dp[u][1]+=min(dp[v][0],dp[v][1]); 
        		minn=min(minn,dp[v][0]-min(dp[v][0],dp[v][1])); 
        	} 
        	dp[u][1]+=minn;
        } 
        int main(){ 
        	cin>>n; 
        	for(int i=1;i<=n;i++){ 
        		cin>>u; 
        		cin>>dp[u][0]; 
        		cin>>n1; 
        		for(int j=1;j<=n1;j++){ 
        			cin>>v; 
        			vc[u].push_back(v); 
        			vc[v].push_back(u); 
        		} 
        	} 
        	dfs(1,0); 
        	cout<<min(dp[1][0],dp[1][1]); 
        }
        
        
        • 0
          @ 2025-7-25 10:09:40
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include<bits/stdc++.h> 
          using namespace std; 
          const int N=1e4+10; 
          const int INF=0x3f3f3f3f; 
          int dp[N][3],n,u,v,n1; 
          vectorvc[N]; 
          void dfs(int u,int fa){ 
          	bool flag=0; 
          	int minn=INF; 
          	for(int i=0;i<vc[u].size();i++){ 
          		int v=vc[u][i]; 
          		if(v==fa)continue; 
          		dfs(v,u); 
          		dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2])); 
          		dp[u][2]+=min(dp[v][0],dp[v][1]); 
          		dp[u][1]+=min(dp[v][0],dp[v][1]); 
          		minn=min(minn,dp[v][0]-min(dp[v][0],dp[v][1])); 
          	} 
          	dp[u][1]+=minn;
          } 
          int main(){ 
          	cin>>n; 
          	for(int i=1;i<=n;i++){ 
          		cin>>u; 
          		cin>>dp[u][0]; 
          		cin>>n1; 
          		for(int j=1;j<=n1;j++){ 
          			cin>>v; 
          			vc[u].push_back(v); 
          			vc[v].push_back(u); 
          		} 
          	} 
          	dfs(1,0); 
          	cout<<min(dp[1][0],dp[1][1]); 
          }
          
          
          • 0
            @ 2025-7-15 15:10:03

            #include<bits/stdc++.h> using namespace std; const int N=1e4+10; const int INF=0x3f3f3f3f; int dp[N][3],n,u,v,n1; vectorvc[N]; void dfs(int u,int fa){ bool flag=0; int minn=INF; for(int i=0;i<vc[u].size();i++){ int v=vc[u][i]; if(v==fa)continue; dfs(v,u); dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2])); dp[u][2]+=min(dp[v][0],dp[v][1]); dp[u][1]+=min(dp[v][0],dp[v][1]); minn=min(minn,dp[v][0]-min(dp[v][0],dp[v][1])); } dp[u][1]+=minn; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>u; cin>>dp[u][0]; cin>>n1; for(int j=1;j<=n1;j++){ cin>>v; vc[u].push_back(v); vc[v].push_back(u); } } dfs(1,0); cout<<min(dp[1][0],dp[1][1]); }

            • 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;
              }
              
              • -2
                @ 2023-4-25 19:42:25
                #include<bits/stdc++.h>
                #define ll long long 
                #define R register
                using namespace std;
                const int N=1e5+85;
                struct E{
                  int nxt,to;
                }e[N];
                int n,num,head[N],rot[N],val[N],root=1,f[N][3];
                inline void add(R int u,R int v){
                    e[++num].to=v;
                    e[num].nxt=head[u];
                    head[u]=num;
                }
                // 监控T的子树   不放0  
                // 可以不监控    不放1
                // 监控T的子树   放 2
                inline void dp(R int pos,R int fa){
                     f[pos][2]=val[pos];
                     R int pd=1,vis=1,cha=0x3f3f3f3f;
                     for(R int i=head[pos];i;i=e[i].nxt){
                        R int v=e[i].to;
                        if(v!=fa){
                        pd=0;
                        dp(v,pos);
                        if(f[v][0]>=f[v][2]){
                        f[pos][0]+=f[v][2];
                        vis=0;
                        }
                        else{
                        f[pos][0]+=f[v][0];
                        cha=min(cha,f[v][2]-f[v][0]);
                        }
                        f[pos][1]+=min(f[v][0],f[v][2]);
                        f[pos][2]+=min(f[v][0],min(f[v][1],f[v][2]));
                        }
                    }
                    if(vis&&pd==0)
                    f[pos][0]+=cha;
                      if(pd){
                    f[pos][0]=val[pos];
                    f[pos][1]=0;
                    f[pos][2]=val[pos];
                    }
                }
                int main(){
                    scanf("%d",&n);
                    for(R int i=1;i<=n;++i){
                        R int p,m,w;
                        scanf("%d%d%d",&p,&w,&m);
                        val[p]=w;
                        for(R int j=1;j<=m;++j){
                           R int k;
                           scanf("%d",&k);
                           add(k,p);add(p,k);
                           rot[k]=1;
                        }
                    }
                    while(rot[root])root++;
                    dp(root,0);
                    printf("%d",min(f[root][0],f[root][2]));
                    return 0;
                }
                
                • 1

                信息

                ID
                474
                时间
                1000ms
                内存
                512MiB
                难度
                6
                标签
                递交数
                153
                已通过
                45
                上传者