#include "race.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
#include <queue>
#include <time.h>
#include <bitset>
#include <unordered_map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ft first
#define sc second
#define add push_back
#define all(v) v.begin(),v.end()
#define mpr make_pair
#define sz(v) (ll)v.size()
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define FORD(i,a,b) for(ll i = (a); i >= (b); i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const ll MOD = 1e9+7;
const ll INF = 1e9;
const int N = 200005;
vector<pll> g[N];
ll answ = -1;
ll entsize[N];
bool used[N];
ll nn = 0;
ll k;
void dfs_sz(int u, int p)
{
nn++;
entsize[u] = 1;
for(auto f : g[u])
{
if(f.ft == p or used[f.ft])
{
continue;
}
dfs_sz(f.ft,u);
entsize[u]+=entsize[f.ft];
}
}
int find_center(int u, int p)
{
int mx_size = -1;
int vert = -1;
for(auto f : g[u])
{
if(f.ft == p or used[f.ft])
{
continue;
}
if(entsize[f.ft] > mx_size)
{
mx_size = entsize[f.ft];
vert = f.ft;
}
}
if(2*mx_size <= nn)
{
return u;
}
return find_center(vert,u);
}
int find_centroid(int u)
{
nn = 0;
dfs_sz(u,u);
int center = find_center(u,u);
dfs_sz(center,center);
return center;
}
vector<pll> mas;
map<ll,ll> mp;
void update(ll o)
{
if(answ == -1 or o < answ)
{
answ = o;
}
}
void solve(int u, int p, int dist, int depth)
{
if(p != u)
{
mas.add(mpr(dist,depth));
}
for(auto f : g[u])
{
if(f.ft == p or used[f.ft])
{
continue;
}
solve(f.ft,u,dist+f.sc,depth+1);
if(p == u)
{
for(auto hg : mas)
{
if(hg.ft > k)
{
continue;
}
else if(hg.ft == k)
{
update(hg.sc);
}
else
{
if(mp.find(k-hg.ft) != mp.end())
{
update(mp[k-hg.ft] + hg.sc);
}
}
}
for(auto hg : mas)
{
if(hg.ft > k)
{
continue;
}
if(mp.find(hg.ft) == mp.end())
{
mp[hg.ft] = hg.sc;
}
else
{
mp[hg.ft] = min(mp[hg.ft], hg.sc);
}
}
mas.clear();
}
}
}
void centroid_decomposition()
{
queue<ll> q;
q.push(1);
while(!q.empty())
{
int vnow = q.front();
q.pop();
mp.clear();
int cen = find_centroid(vnow);
solve(cen,cen,0,0);
used[cen] = 1;
for(auto f : g[cen])
{
if(used[f.ft] or entsize[f.ft] == 1)
{
continue;
}
q.push(f.ft);
}
}
}
int best_path(int n, int K, int H[][2], int L[])
{
k = K;
FOR(i,0,n-1)
{
g[H[i][0]].add(mpr(H[i][1],L[i]));
g[H[i][1]].add(mpr(H[i][0],L[i]));
}
centroid_decomposition();
return answ;
}
// int main()
// {
// int l[] = {3,4,5,4,6,3,2,5,6,7};
// int h[][2] = {{0,1}, {0,2}, {2,3}, {3,4}, {4,5}, {0,6}, {6,7}, {6,8}, {8,9}, {8,10}};
// cout<<best_path(11,12,h,l)<<endl;
// //int l[] = {1,1};
// //int h[][2] = {{0,1},{1,2}};
// //cout<<best_path(3,3,h,l)<<endl;
// return 0;
// }
/*
░▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░
▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒
▓▓▓▒░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▒░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▒░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░░░▒▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▒░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▒░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▒░▒▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▒░░▒▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░░▒▓▓▓▓▓
▓▓▓▓▓▒░░░░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░░▒▓▓▓
▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓
▓▓▓▓▓▒░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓
▓▓▓▓▓▓▒░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░▒▓▓▓▓
▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒
░▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░
⠀⠀⠀⠀⠀
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4952 KB |
Output is correct |
11 |
Correct |
3 ms |
5000 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4980 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4952 KB |
Output is correct |
11 |
Correct |
3 ms |
5000 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4980 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4964 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
4 ms |
5068 KB |
Output is correct |
22 |
Correct |
4 ms |
5016 KB |
Output is correct |
23 |
Correct |
4 ms |
5016 KB |
Output is correct |
24 |
Correct |
6 ms |
5016 KB |
Output is correct |
25 |
Correct |
6 ms |
5196 KB |
Output is correct |
26 |
Correct |
4 ms |
5016 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
5 ms |
5068 KB |
Output is correct |
29 |
Correct |
5 ms |
5148 KB |
Output is correct |
30 |
Correct |
5 ms |
5068 KB |
Output is correct |
31 |
Correct |
5 ms |
5068 KB |
Output is correct |
32 |
Correct |
5 ms |
5068 KB |
Output is correct |
33 |
Correct |
5 ms |
5068 KB |
Output is correct |
34 |
Correct |
4 ms |
5068 KB |
Output is correct |
35 |
Correct |
4 ms |
5136 KB |
Output is correct |
36 |
Correct |
5 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
5 ms |
5068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4952 KB |
Output is correct |
11 |
Correct |
3 ms |
5000 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4980 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4964 KB |
Output is correct |
19 |
Correct |
304 ms |
13280 KB |
Output is correct |
20 |
Correct |
298 ms |
13268 KB |
Output is correct |
21 |
Correct |
294 ms |
13284 KB |
Output is correct |
22 |
Correct |
266 ms |
13292 KB |
Output is correct |
23 |
Correct |
145 ms |
13712 KB |
Output is correct |
24 |
Correct |
97 ms |
12388 KB |
Output is correct |
25 |
Correct |
225 ms |
20736 KB |
Output is correct |
26 |
Correct |
147 ms |
20720 KB |
Output is correct |
27 |
Correct |
271 ms |
20168 KB |
Output is correct |
28 |
Correct |
658 ms |
36376 KB |
Output is correct |
29 |
Correct |
653 ms |
36368 KB |
Output is correct |
30 |
Correct |
278 ms |
20076 KB |
Output is correct |
31 |
Correct |
279 ms |
20164 KB |
Output is correct |
32 |
Correct |
399 ms |
20276 KB |
Output is correct |
33 |
Correct |
494 ms |
20852 KB |
Output is correct |
34 |
Correct |
427 ms |
20800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4952 KB |
Output is correct |
11 |
Correct |
3 ms |
5000 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4980 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4964 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
4 ms |
5068 KB |
Output is correct |
22 |
Correct |
4 ms |
5016 KB |
Output is correct |
23 |
Correct |
4 ms |
5016 KB |
Output is correct |
24 |
Correct |
6 ms |
5016 KB |
Output is correct |
25 |
Correct |
6 ms |
5196 KB |
Output is correct |
26 |
Correct |
4 ms |
5016 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
5 ms |
5068 KB |
Output is correct |
29 |
Correct |
5 ms |
5148 KB |
Output is correct |
30 |
Correct |
5 ms |
5068 KB |
Output is correct |
31 |
Correct |
5 ms |
5068 KB |
Output is correct |
32 |
Correct |
5 ms |
5068 KB |
Output is correct |
33 |
Correct |
5 ms |
5068 KB |
Output is correct |
34 |
Correct |
4 ms |
5068 KB |
Output is correct |
35 |
Correct |
4 ms |
5136 KB |
Output is correct |
36 |
Correct |
5 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
5 ms |
5068 KB |
Output is correct |
39 |
Correct |
304 ms |
13280 KB |
Output is correct |
40 |
Correct |
298 ms |
13268 KB |
Output is correct |
41 |
Correct |
294 ms |
13284 KB |
Output is correct |
42 |
Correct |
266 ms |
13292 KB |
Output is correct |
43 |
Correct |
145 ms |
13712 KB |
Output is correct |
44 |
Correct |
97 ms |
12388 KB |
Output is correct |
45 |
Correct |
225 ms |
20736 KB |
Output is correct |
46 |
Correct |
147 ms |
20720 KB |
Output is correct |
47 |
Correct |
271 ms |
20168 KB |
Output is correct |
48 |
Correct |
658 ms |
36376 KB |
Output is correct |
49 |
Correct |
653 ms |
36368 KB |
Output is correct |
50 |
Correct |
278 ms |
20076 KB |
Output is correct |
51 |
Correct |
279 ms |
20164 KB |
Output is correct |
52 |
Correct |
399 ms |
20276 KB |
Output is correct |
53 |
Correct |
494 ms |
20852 KB |
Output is correct |
54 |
Correct |
427 ms |
20800 KB |
Output is correct |
55 |
Correct |
22 ms |
6084 KB |
Output is correct |
56 |
Correct |
18 ms |
5964 KB |
Output is correct |
57 |
Correct |
176 ms |
13736 KB |
Output is correct |
58 |
Correct |
47 ms |
11748 KB |
Output is correct |
59 |
Correct |
321 ms |
25164 KB |
Output is correct |
60 |
Correct |
1179 ms |
47308 KB |
Output is correct |
61 |
Correct |
354 ms |
20340 KB |
Output is correct |
62 |
Correct |
351 ms |
20292 KB |
Output is correct |
63 |
Correct |
503 ms |
20168 KB |
Output is correct |
64 |
Correct |
1169 ms |
26928 KB |
Output is correct |
65 |
Correct |
532 ms |
21436 KB |
Output is correct |
66 |
Correct |
913 ms |
36636 KB |
Output is correct |
67 |
Correct |
145 ms |
18648 KB |
Output is correct |
68 |
Correct |
549 ms |
25676 KB |
Output is correct |
69 |
Correct |
553 ms |
25476 KB |
Output is correct |
70 |
Correct |
483 ms |
24748 KB |
Output is correct |