I got a AC, but it's O(n³).

I'll try — but I guess it will be not a very clear explanation :)

Let's build a centriod decomposition of a tree. Now every vertex have it's level — root of a tree (rank 0) divides it in few subtrees, every subtree have it's own root (rank 1), which is dividing it in new subtrees etc.

We are interested in connected subgraphs of a tree. Let's fix main vertex V which belongs to our subgraph and have highest level in decomposition hierarchy among all vertices forming a subgraph. There can't be two such vertices in our subgraph — because every path between two vertices of rank X containts at least one vertex of rank X-1. Therefore every possible connected subgraph is uniquely described by its main vertex V and completely belongs to subtree of V in decomposition.

Now we have to solve a bit easier problem for this vertex V and its subtree — you have to solve your connected subgraph knapsack task on a tree, but root of a tree have to be taken. Sort vertices in order of traversal and you will get almost classical knapsack :) For every vertex Q, you may either take it (and move to next vertex in order of traversal) or not take it — but in this case you also can't take vertices in subtree of Q now, so you have to move straight to the first vertex outside subtree of Q.

It gives us O(N * K) solution for a subtask, where K is size of knapsack and N is size of subtree. Overall size of subtrees at one level is O(n), and you have O(log(n)) levels in centriod decomposition. Overall complexity is O(n * K * log(n)).

A little bit different explanation which does not start with the centriod decomposition but rather comes to it naturally:

Let's pick an arbitrary vertex v and make it a root of the tree. Under the assumption that it is the root and that we take it, we can solve this problem in O(|V| * m) time using the following idea: when we enter a vertex, we can do two things:

1. Do not take it. In this case, we can't take any of its children(because we assume that the root is taken).

2. Take it and do something with its children. The order of visiting children does not matter, so we can pass the same vector around. Here is a piece of code which implements it:

   void dfs2(int v, int p, vector<int>& dp) {
       // dpAt[v] corresponds to the case when we take v.
       fill(dpAt[v].begin(), dpAt[v].end(), -INF);
       for (int i = cost[v]; i <= m; i++)
           dpAt[v][i] = dp[i - cost[v]] + val[v]; 
       for (int to : g[v])
           if (to != p && !bad[to]) 
               // Important note: we pass the same vector to the children,
               // which gets updated properly inside them. 
               dfs2(to, v, dpAt[v]);
       // dp corresponds to the case when we do not take it.
       // We choose the best of two options.
       for (int i = 0; i <= m; i++)
           dp[i] = max(dp[i], dpAt[v][i]);
   }
   
   ...
   dfs2(root, root, vector with zeros)

These observations lead to an obvious O(n^2 * m) solution: we can just test all possible roots. But it is still not good enough. One more observation: if we do not pick v, we can simply delete it from the tree and solve the problem independently for smaller trees. That's it. So the final solution is:

1. Pick a "good" vertex(like in the centriod decomposition).

2. Run the algorithm described above by making it a root.

3. Delete it from the tree and solve smaller subproblems recursively.

The time complexity is O(n * m * log n)(there are O(log n) levels and each vertex is processed at most once per level).

I see your point, but that seems to be 'over-fair' to get out of T-shirt zone because of my own comment about test data missing in your contest. After all that's not my job to look for missing test cases.

Please get me right, I'm not asking for this particular T-shirt, it's just me being surprised a bit about such a scenario. In my (quite limited) experience that is the first contest I see where something is going on after the contest is finished for several days.

Anyway probably my main concern is that it was done quietly behind the scenes, at least you could reply to my comment about your test data missing. Otherwise I have already added this one to my list "T-shirts to come" and had no idea that there was some rejudge afterwards.

Anyway, on the positive side, I'd like to thank you and contest setter for great problems (in this particular contest and previous weekly challenges where I took part).