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

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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