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

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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