#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){
if(X>Y) swap(X,Y);
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<ll> ax(N,0),ay(N,0),l1(N),l2(N);
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});
}
}
}
l1[0]=min(ax[0],ay[0]);
l2[0]=max(ax[0],ay[0])-l1[0];
for(int i=1; i<N; i++){
l1[i]=min(ax[i],ay[i])+l1[i-1];
l2[i]=max(ax[i],ay[i])-min(ax[i],ay[i])+l2[i-1];
}
int rez=0;
for(int l=0; l<=X; l++){
for(int r=Y; r<N; r++){
ll sum=l1[r];
if(l!=0) sum-=l1[l-1];
if(sum<=k){
int m=0,a=l+1,b=l;
while(b<=r){
ll c=l2[b]-l2[a-1];
if(sum+c<=k){
m=max(m,b-a+1);
b++;
}else{
a++;
}
}
rez=max(rez,r-l+1+m);
}else{
int m=1e9,a=X+1,b=X+1;
while(b<r){
ll c=l1[b]-l1[a-1];
if(sum-c<=k){
m=min(m,b-a+1);
a++;
}else{
b++;
}
}
rez=max(rez,r-l+1-m);
}
}
}
return rez;
}
/*
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... |