typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
int n,k;
int sub[200000];
vector<pair<int,int>>komsu[200000];
void dfs(int pos,int par){
sub[pos]=1;
for(auto x:komsu[pos]){
if(x.fr==par||sub[x.fr]==-1)continue;
dfs(x.fr,pos);
sub[pos]+=sub[x.fr];
}
}
int deco(int pos){
dfs(pos,pos);
int total=sub[pos];
while(true){
int nex=-1;
for(auto x:komsu[pos]){
if(sub[x.fr]==-1)continue;
if(sub[x.fr]>sub[pos])continue;
if(sub[x.fr]>total/2){
nex=x.fr;
break;
}
}
if(nex==-1)break;
pos=nex;
}
sub[pos]=-1;
map<ll,int>mp;
int res=sonsuz;
queue<array<ll,4>>q;
for(auto y:komsu[pos]){
if(sub[y.fr]==-1)continue;
q.push({y.fr,y.sc,1,pos});
while(q.size()){
int loc=q.front()[0],dis=q.front()[1],adim=q.front()[2],las=q.front()[3];
q.pop();
if(dis>k)continue;
if(mp[k-dis])res=min(res,adim+mp[k-dis]);
for(auto x:komsu[loc]){
if(x.fr==las)continue;
if(sub[x.fr]==-1)continue;
q.push({x.fr,dis+x.sc,adim+1,loc});
}
}
q.push({y.fr,y.sc,1,pos});
while(q.size()){
int loc=q.front()[0],dis=q.front()[1],adim=q.front()[2],las=q.front()[3];
q.pop();
if(dis>k)continue;
if(mp[dis]==0){
mp[dis]=adim;
}
else mp[dis]=min(mp[dis],adim);
for(auto x:komsu[loc]){
if(x.fr==las)continue;
if(sub[x.fr]==-1)continue;
q.push({x.fr,dis+x.sc,adim+1,loc});
}
}
}
if(mp[k])res=min(res,mp[k]);
for(auto x:komsu[pos]){
if(sub[x.fr]==-1)continue;
res=min(res,deco(x.fr));
}
return res;
}
int best_path(int N,int K,int H[][2],int L[]){
n=N;
k=K;
for(int i=0;i<n-1;i++){
komsu[H[i][0]].pb({H[i][1],L[i]});
komsu[H[i][1]].pb({H[i][0],L[i]});
}
int ans=deco(1);
if(ans==sonsuz)return -1;
return ans;
}
# | 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... |