#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<pair<int, int>>> adj;
vector<bool> visited;
vector<int> distX, distY;
void dfs(int curr, int d, vector<int> &dist){
visited[curr] = true;
dist[curr] =d;
for(pair<int, int> u : adj[curr]){
if(!visited[u.first]){
dfs(u.first, d+u.second, dist);
}
}
}
int solve(int N, int K, int mx){
int ans = 0;
priority_queue<pair<int, int>> q;
for(int i = 0; i < N; i++){
q.push({min(distX[i], distY[i]), i});
}
vector<int> cnt(N, 0);
while(!q.empty()){
while(!q.empty() && (K < q.top().first || cnt[q.top().second] > mx-1)) q.pop();
if(q.empty()) break;
int t = q.top().first;
int x = q.top().second;
q.pop();
ans++;
cnt[x]++;
K-=t;
if(cnt[x]==1 && mx == 2){
q.push({abs(distX[x] - distY[x]), x});
}
}
if(K<0) return 0;
else return ans;
}
int max_score(int N, int X, int Y, int K, vector<int> U, vector<int> V, vector<int> W){
adj.assign(N, vector<pair<int, int>>(0));
for(int i = 0; i < N-1; i++){
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
distX.resize(N, 0);
distY.resize(N, 0);
visited.assign(N, false);
dfs(0, 0, distX);
visited.assign(N, false);
dfs(0, 0, distY);
return max(solve(N, K, 1), solve(N, K, 2));
}
signed main(){ // ONLY TESTING
int N, X, Y;
int K;
vector<int> U(N), V(N), W(N);
cin >> N >> X >> Y >> K;
for(int i = 0; i < N-1; i++){
cin >> U[i];
}
for(int i = 0; i < N-1; i++){
cin >> V[i];
}
for(int i = 0; i < N-1; i++){
cin >> W[i];
}
cout << max_score(N, X, Y, K, U, V, W) << "\n";
}
Compilation message
closing.cpp: In function 'int main()':
closing.cpp:69:20: warning: 'N' is used uninitialized in this function [-Wuninitialized]
69 | vector<int> U(N), V(N), W(N);
| ^
/usr/bin/ld: /tmp/ccMqxiCC.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cct3kzmB.o:closing.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccMqxiCC.o: in function `main':
grader.cpp:(.text.startup+0x6a1): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
