52 lines
1.2 KiB
C++
52 lines
1.2 KiB
C++
// lanqiao 3029 卖树
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
using ll = long long;
|
|
const int N = 1e5 + 9;
|
|
vector<int> g[N];
|
|
int dep1[N], depU[N], depV[N];
|
|
void dfs(int x, int fa, int dep[]){
|
|
dep[x] = dep[fa] + 1;
|
|
for(const auto &y:g[x]){
|
|
if(y == fa) continue;
|
|
dfs(y, x, dep);
|
|
}
|
|
}
|
|
void solve(){
|
|
ll n, k, c; cin >> n >> k >> c;
|
|
for(int i = 1; i < n; i++){
|
|
int u, v; cin >> u >> v;
|
|
g[u].push_back(v), g[v].push_back(u);
|
|
}
|
|
dep1[0] = depU[0] = depV[0] = -1;
|
|
dfs(1, 0, dep1);
|
|
// 得到U
|
|
int U = 1;
|
|
for(int i = 1; i <= n; i++) if(dep1[i] > dep1[U]) U = i;
|
|
dfs(U, 0, depU);
|
|
int V = 1;
|
|
for(int i = 1; i <= n; i++) if(depU[i] > depU[V]) V = i;
|
|
dfs(V, 0, depV);
|
|
// 枚举所有点计算价值和代价
|
|
ll ans = 0;
|
|
for(int i = 1; i <= n; i++){
|
|
// 价值 = 以 i 为根的树的所有点的最大深度， 即max(depU[i], depV[i])
|
|
// 代价 = 从1走到i的代价
|
|
ans = max(ans, max(depU[i], depV[i])*k - dep1[i]*c);
|
|
}
|
|
cout << ans << endl;
|
|
|
|
// 多组测试数据，需要重置
|
|
for(int i = 1; i <= n; i++) g[i].clear();
|
|
}
|
|
int main(){
|
|
int t; cin >> t;
|
|
while(t--) solve();
|
|
return 0;
|
|
}
|
|
/* test samples -> 4
|
|
1
|
|
3 4 5
|
|
1 2
|
|
1 3
|
|
*/ |