#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MOD 1000000007
int max_score(int N, int X, int Y, ll k, vector<int> U, vector<int> V, vector<int> W){
vector<pair<int,int>> c[N];
for(int i=0; i<N-1; i++){
c[U[i]].pb({V[i],W[i]});
c[V[i]].pb({U[i],W[i]});
}
vector<int> ax(N,0),ay(N,0);
stack<pair<int,int>> s;
s.push({X,0});
while(!s.empty()){
pair<int,int> cur=s.top();
s.pop();
for(int i=0; i<c[cur.fi].size(); i++){
if(ax[c[cur.fi][i].fi]==0 && c[cur.fi][i].fi!=X){
ax[c[cur.fi][i].fi]=cur.se+c[cur.fi][i].se;
s.push({c[cur.fi][i].fi,cur.se+c[cur.fi][i].se});
}
}
}
s.push({Y,0});
while(!s.empty()){
pair<int,int> cur=s.top();
s.pop();
for(int i=0; i<c[cur.fi].size(); i++){
if(ay[c[cur.fi][i].fi]==0 && c[cur.fi][i].fi!=Y){
ay[c[cur.fi][i].fi]=cur.se+c[cur.fi][i].se;
s.push({c[cur.fi][i].fi,cur.se+c[cur.fi][i].se});
}
}
}
int r=0;
for(int sx=0; sx<=X; sx++){
for(int bx=X; bx<N; bx++){
for(int sy=0; sy<=Y; sy++){
for(int by=Y; by<N; by++){
ll sum=0;
for(int i=0; i<N; i++){
if(i>=sx && i<=bx && i>=sy && i<=by) sum+=max(ax[i],ay[i]);
else if(i>=sx && i<=bx) sum+=ax[i];
else if(i>=sy && i<=by) sum+=ay[i];
}
if(sum<=k){
r=max(r,bx+by-sx-sy+2);
}
}
}
}
}
return r;
}
/*
int main()
{
fastIO;
int t=1;
cin>>t;
while(t--){
int n,x,y;
ll k;
cin>>n>>x>>y>>k;
vector<int> U(n), V(n), W(n);
for(int i=0; i<n-1; i++){
cin>>U[i]>>V[i]>>W[i];
}
cout<<max_score(n,x,y,k,U,V,W)<<'\n';
}
return 0;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |