1822F - Gardening Friends - CodeForces Solution

#include<bits/stdc++.h>
#define endl '\n'
#define OuO ios::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define int long long
using namespace std;

void solve(){
    int n, k, c;
    ll ans = 0;
    cin >> n >> k >> c;
    vector<vector<int>> g(n);
    for(int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    auto bfs = [&](int s){
        vector<int> d(n, -1);
        queue<int> q;
        q.push(s);
        d[s] = 0;

        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(auto x: g[now]){
                if(d[x] != -1) continue;
                d[x] = d[now] + 1;
                q.push(x);
            }
        }

        return d;
    };
    vector<int> one = bfs(0);
    int t = max_element(one.begin(), one.end()) - one.begin();
    vector<int> sec = bfs(t);

    if(c >= k){
        for(int i = 0; i  < n; ++i){
            ans = max(ans, 1LL * one[i] * k);
        }
    }else{
        for(int i = 0; i < n; ++i){
            ans = max(ans, 1LL * sec[i] * k - one[i] * c);
        }
    }
    cout << ans << endl;
}

signed main(){OuO
    int tt;
    cin >> tt;
    while(tt--) solve();
}