solutionA_dp.cpp

#include <bits/stdc++.h>
using namespace std;

vector<int> alpha, valu, beta;
vector<vector<int>> adj, adj_mat, dp;

void dfs(int a, int par, vector<int> &vis) {
    for (auto val : adj[a]) {
        if (val != par) {
            vis[val] = 1;
            dfs(val, a, vis);
        }
    }
}

void dp_dfs(int a, int par){
    for (auto val : adj[a]) {
        if (val != par) {
            dp_dfs(val, a);
            for (int i = 0; i <= alpha[a]; i++) {
                int p;
                for (int j = 0; j <= alpha[val]; j++) {
                    int no = dp[val][j] - i*j*adj_mat[a][val];
                    if(j == 0){
                        p = no;
                    }
                    p = max(p, no);
                }
                dp[a][i] += p;
            }
        }
    }

    for (int i = 0; i <= alpha[a]; i++) {
        dp[a][i] += i*valu[a] - i*i*adj_mat[a][a];
    }
}

void backtrack_dp(int a, int  par, int ans){
    // checking beta for node 'a'
    for (int i = 0; i <= alpha[a]; i++) {
        if(dp[a][i] == ans){
            beta[a] = i;
            break;
        }
    }

    int ind = beta[a];

    for(auto val : adj[a]){
        if(val != par){
            int p, store;
            for (int j = 0; j <= alpha[val]; j++) {
                int no = dp[val][j] - ind*j*adj_mat[a][val];
                if(j == 0){
                    p = no;
                    store = j;
                }
                if(no > p){
                    p = no;
                    store = j;
                }
            }
            backtrack_dp(val, a, dp[val][store]);
        }
    }
}

void solve() {
    int n, a, b;
    cin>>n;

    for (int i = 0; i < n; i++) {
        cin>>a>>b;
        alpha.push_back(a);
        valu.push_back(b);
    }

    adj.resize(n+2);  // adjacency list
    adj_mat.resize(n+2,vector<int> (n+2,0));  // adjacency matrix

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin>>a;
            if(i < j && a != 0){
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
            adj_mat[i][j] = a;
            adj_mat[j][i] = a;
        }
    }

    int no_of_comp = 0;
    vector<int> vis(n+2, 0);   // visited array

    // dfs to calculate number of components
    for (int i = 0; i < n; i++) {
        if(vis[i] == 0){
            vis[i] = 1;
            dfs(i, -1, vis);
            no_of_comp++;
        }
    }

    cout<<no_of_comp<<endl;

    dp.resize(n+2,vector<int> (11,0));
    // dp taking 0 as root
    dp_dfs(0, -1);

    int ans = 0;
    for (int i = 0; i <= alpha[0]; i++) {
        ans = max(ans, dp[0][i]);
    }

    cout<<ans<<endl;

    // backtracking to output beta values
    beta.resize(n+2,-1);
    backtrack_dp(0, -1, ans);

    for (int i = 0; i < n; i++) {
        cout<<beta[i]<<" ";
    }
    cout<<endl;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}