Trouble with a variant of 2014F: Sheriff's Defence

#	User	Rating
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	Um_nik	3396

#	User	Contrib.
1	Um_nik	164
2	cry	161
3	maomao90	160
4	-is-this-fft-	159
5	atcoder_official	158
5	awoo	158
7	adamant	155
8	nor	154
9	maroonrk	152
10	Dominater069	149

This problem was the first time I encountered a problem of DP on trees, and even with a decent amount of practice in DP, the states similar to that of "maximim score in the subtree of j considering j is taken or not", did not occur to me during the contest probably because such a state breaks quite easily when the coins are taken from let's say all the neighbours at a distance of <= 2.

This is the best I could come up with for the above variation:

given a tree and it's node values, you can pick a node but all it's neighbours upto a distance of 2 gets subtracted by c, find max sum of node values you can achieve

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

void solve() {
    int n, c; cin >> n >> c;
    vector<vector<int>> adj (n);
    vector<int> a (n); for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<vector<int>> dp (1 << 2, vector<int> (n)); //dp[i][j] = maximum coins from the subtree of j when i type of influence is faced by the parent
    //0: influence of no nodes in the subtree reach the parent
    //1: influence of the children only reaches the parent
    //2: influence of the current node only reach the parent (also means the current node is active)
    //3: influence of the current node and the children reach the parent (curr node active)
    auto dfs = [&] (auto&& self, i64 v, i64 p) -> void {
        dp[2][v] = a[v];
        dp[3][v] = a[v];
        for (i64 u: adj[v]) {
            if (u == p) continue;
            self(self, u, v);
            dp[0][v] += max(dp[1][u], dp[0][u]);
            dp[1][v] += max(dp[2][u], dp[3][u]);
            dp[2][v] += max(dp[1][u] - 2 * c, dp[0][u]);
            dp[3][v] += max(dp[2][u] - 2 * c, dp[3][u] - 4 * c);
        }
    };
    dfs(dfs, 0, -1);
    cout << max({dp[0][0], dp[1][0], dp[2][0], dp[3][0]}) << '\n';
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}

The above solution is wrong for the above problem, counterexamples are plenty. The reason is because the code only takes care of influence of children passed onto its parents, however it is easy to see that a node once picked not only influences it's children and parent, but also it's siblings, which is not taken care of. This is where the difference from the actual problem becomes apparent. Influence upto one units do not affect the siblings, hence the same state works for neighbour-only influence.

As a side effect however, the code works perfectly for a linear graph, i.e a tree with single children only, thus this code can be thought of as the solution to the problem when we have an array and we can pick elements at the cost of reducing it's neighbours upto 2 indices on both sides by c, with the goal to maximise the score.

Anyone knows any standard procedure for such problems?

Aspergillus's blog