#define mocua(inp, out) if(fopen(inp,"r")){freopen(inp,"r",stdin);freopen(out,"w",stdout);}
#include <iostream>
#include <cstdint>
#include <climits>
#include <vector>
#include <cstring>
using namespace std;
int numNode, desiredLength;
vector<int> e[int(2e5+3)];
vector<pair<int,int>> elen[int(2e5+3)];
bool removed[int(2e5+3)];
int sz[int(2e5+3)];
int resize(int u, int p=-1){
sz[u] = 1;
for(int &v : e[u])
if(!removed[v] && v!=p)
sz[u] += resize(v, u);
return sz[u];
}
int find_centroid(int targetsize, int u, int p=-1){
for(int &v : e[u])
if(!removed[v] && v!=p){
if(sz[v] > targetsize) return find_centroid(targetsize, v, u);
}
return u;
}
const int LIM = 1e6;
int mp[LIM+3];
int ans = 1e9+69;
void progress(bool isUpd, int current_length, int depth, int u, int p=-1){
if(isUpd) mp[current_length] = min(mp[current_length], depth);
else{
int f = desiredLength - current_length;
if(f>=0)
ans = min(ans, mp[f]+depth);
// cout << u << ' ' << current_length << ' ' << mp[f] << '+' << depth[u] << '\n';
}
for(auto &[v,w] : elen[u])
if(!removed[v] && v!=p){
progress(isUpd, current_length+w, depth+1, v, u);
}
}
void centroid_decomp(int u=0){
u = find_centroid(resize(u)>>1, u);
removed[u] = 1;
// cout << "CENTROID " << u << '\n';
memset(mp, 0x3f, sizeof mp);
mp[0] = 0;
for(auto &[v,w] : elen[u])
if(!removed[v]){
progress(0, w, 1, v);
progress(1, w, 1, v);
}
for(int &v : e[u])
if(!removed[v])
centroid_decomp(v);
}
int best_path(int _numNode, int _desiredLength, int edge[][2], int edgeLength[]){
numNode = _numNode;
desiredLength = _desiredLength;
for(int i=0; i<numNode-1; ++i){
e[edge[i][0]].emplace_back(edge[i][1]);
e[edge[i][1]].emplace_back(edge[i][0]);
elen[edge[i][0]].emplace_back(edge[i][1], edgeLength[i]);
elen[edge[i][1]].emplace_back(edge[i][0], edgeLength[i]);
}
centroid_decomp();
return (ans>=1e9 ? -1 : ans);
}
// int edge[int(2e5+3)][2];
// int edgeLength[int(2e5+3)];
// signed main()
// {
// cin.tie(0) -> sync_with_stdio(0);
// int n, k;
// cin >> n >> k;
// for(int i=0, u, v; i<n-1; ++i) cin >> edge[i][0] >> edge[i][1];
// for(int i=0; i<n-1; ++i) cin >> edgeLength[i];
// cout << best_path(n, k, edge, edgeLength);
// 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... |