I found an unusual similarity between three problems: a POI 2016 task, an Educational F, and a Div. 3 G. While these problems are formulated in different ways, they can be solved in incredibly similar ways. I'm not claiming foul play; this is likely a case of parallel thinking. Spoilers ahead.

POI 2016 Parade

Author: Unknown

This task was the oldest one. The task can be summed up as follows: Given a tree, choose a path that maximizes the number of "adjacent" edges. "Adjacent" as in one of its endpoints is in the path, while the other is not. The path has to consist of 2 or more nodes.

For a given path $$$v_1, v_2, ..., v_k$$$, the number of adjacent edges is $$$(\sum_{i=1}^{k} deg(v_i) - 2) + 2$$$. This is because for each node, its contribution is its incident edges, except the $$$2$$$ which are on the path. The $$$2$$$ at the end is to compensate for the ends of the path which only have one neighbor in the path. So let $$$dp(u)$$$ be the best path from the node $$$u$$$ to a node in its subtree. The transitions are: $$$dp(u)$$$ = $$$deg(u) - 2 + \max dp(v, 0)$$$, or $$$0$$$ if $$$u$$$ is a leaf. The answer will simply be the maximum $$$dp(u) + 2$$$ or maximum $$$deg(u) + dp(v_1) + dp(v_2)$$$ for $$$v_1$$$ and $$$v_2$$$ being $$$2$$$ distinct children of $$$u$$$. There is an edge case where the tree is a star. (We have to subtract 1 from the answer).

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC target("popcnt")
using namespace __gnu_pbds;
using namespace std;
template<typename T> using ordered_set = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define popcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()

vector<int> adj[200'000];
int dp[200'000], ans = -1000;

void dfs(int u = 0, int p = -1) {
    int mx1 = 0, mx2 = 0;
    for (int v : adj[u]) if (v != p) {
        dfs(v, u);
        if (dp[v] >= mx1) {
            swap(mx1, mx2);
            mx1 = dp[v];
        } else mx2 = max(mx2, dp[v]);
    }
    dp[u] = mx1 + adj[u].size() - 2;
    ans = max(ans, mx1 + mx2 + (int)adj[u].size() - 2);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u,v; cin >> u >> v;
        adj[--u].push_back(--v);
        adj[v].push_back(u);
    }
    dfs();
    ans += 2;
    int leaves = 0;
    for (int i = 0; i < n; i++) leaves += adj[i].size() == 1;
    if (leaves >= n-1) ans--;
    cout << ans;
}

Education Round 74 1238F - The Maximum Subtree (rated 2200)

Author: Roms

The problem is as follows: Define a good tree as a tree such that for each node, we can assign it a segment, and two nodes will share and edge iff their segments intersect. (As in there exists a point that belongs to both of them). You have to find the largest possible good subtree (connected subgraph) of the given tree.

The most crucial observation is as follows: in a good tree, each node has at most $$$2$$$ non-leaf neighbors. Its leaf neighbors will be contained in its segment, and its $$$1$$$ or $$$2$$$ non-leaf neighbors will share one of its endpoints. If there are $$$3$$$ non-leaf neighbors, They would have to form a cycle. So every good subtree corresponds to a path in the original tree, and the value of a path is equal to $$$(\sum_{i=1}^{k} deg(v_i) - 1) + 2$$$. Sound familiar? We can write the same DP, just with $$$-1$$$ instead of $$$-2$$$. Code can be found 296277443

Codeforces Round 991 (Div. 3) 2050G - Tree Destruction

Author: AVdovin

This problem is suspiciously similar to Parade. Given a tree, find the biggest number of connected components you choose a path and delete all nodes and edges in it. This problem is equivalent to the POI problem, the only difference is that you can choose a path with $$$1$$$ node. Code is 296277443. Note: the number of different characters between 296277443 and 296278465 is only 2 (!).