1822F - Gardening Friends, Subtree DP

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vpi;
typedef pair<int, int> pi;
#define f first
#define s second
#define pb push_back
#define endl "\n"
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
const int mod1 = 1e9 + 7, mod2 = 998244353, INF = 2e18, N = 2e5 + 5, L = 19;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
// -----------------------------------------------------------------------------

void solve()
{
    int n, k, c;
    cin >> n >> k >> c;
    vi adj[n + 1];
    for (int i = 1; i <= (n - 1); i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vi dep(n + 1, 0), ht(n + 1, 0);
    // depth from root, ht of subtree rooted at u
    function<void(int, int, int)> dfs1 = [&](int u, int d, int p)
    {
        dep[u] = d;
        ht[u] = -1;
        for (auto v : adj[u])
        {
            if (v != p)
            {
                dfs1(v, d + 1, u);
                ht[u] = max(ht[u], ht[v]);
            }
        }
        ht[u]++;
    };
    dfs1(1, 0, 0);
    int ans = 0;
    function<void(int, int, int)> dfs2 = [&](int u, int val, int p)
    {
        // val is max distance from node u, which is not in it's subtree
        vi x;
        x.pb(val);
        for (auto v : adj[u])
        {
            if (v != p)
            {
                x.pb(ht[v] + 1);
            }
        }
        sort(all(x));
        ans = max(ans, x.back() * k - dep[u] * c);
        for (auto v : adj[u])
        {
            if (v != p)
            {
                if (ht[v] + 1 == x.back())
                {
                    // means it came from u's subtree
                    dfs2(v, x[x.size() - 2] + 1, u);
                }
                else
                {
                    // means it came from u's subtree
                    dfs2(v, x[x.size() - 1] + 1, u);
                }
            }
        }
    };
    dfs2(1, 0, 0);
    cout << ans << endl;
    return;
}

signed main()
{
    // __START__;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    // __END__;
    return 0;
}