| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1302993 | erali | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
/*
███████╗██████╗ █████╗
██╔════╝██╔══██╗██╔══██╗
███████╗██████╔╝███████║ --- incredible
██╔════╝██╔═══╝ ██╔══██║
███████╗██║ ██║ ██║
╚══════╝╚═╝ ╚═╝ ╚═╝
problem:A
contest:DIV-3
*/
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define int ll
#define sz() size()
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
#define pb push_back
#define popb pop_back
#define ss sort
#define rr reverse
#define pii pair <int, int>
#define pll pair <ll, ll>
using namespace std;
using ld = long double;
using ll = long long;
const int N = 2e5+10;
const ll inf = 1e18;
const int Mod = 1e9+7;
int n, k, uu[N], vv[N];
int sz[N];
int bc[N];
vector <int> eul;
int tin[N], tout[N];
vector <int> g[N];
int dep[N], dep1[N];
int col;
int ans[N];
map <pii, int> rib;
map <int, int> cnt;
map <int, int> mp;
int mn = inf;
void calc(int v, int p)
{
eul.pb(v);
tin[v] = eul.sz()-1;
for (auto to : g[v])
{
if (to != p)
{
dep[to] = dep[v] + rib[{v, to}];
dep1[to] = dep1[v] + 1;
calc(to, v);
sz[v] += sz[to];
if (sz[bc[v]] < sz[to])
{
bc[v] = to;
}
}
}
tout[v] = eul.sz()-1;
}
void add(int v, int p)
{
cnt[dep[v]] ++;
mp[dep[v]] = min(mp[dep[v]], dep1[v] - dep1[p] + 1);
}
void calc_col(int v, int to)
{
if (k - (dep[to] - dep[v]) > 0)
{
if (cnt[dep[v] + (k - (dep[to] - dep[v]))] > 0)
{
mn = min(mn, mp[dep[v] + (k - (dep[to] - dep[v]))] + (dep1[to] - dep1[v]));
// if (mn == 0) cout << v << ' ' << to << ' ' << mp[dep[v] + (k - (dep[to] - dep[v]))] << '\n';
}
}
}
void dfs(int v, int p, int keep)
{
for (auto to : g[v])
{
if (to == p || to == bc[v]) continue;
dfs(to, v, 0);
}
if (bc[v])
{
dfs(bc[v], v, 1);
}
for (auto to : g[v])
{
if (to == p || to == bc[v]) continue;
for (int i = tin[to]; i <= tout[to]; ++i)
{
calc_col(v, eul[i]);
}
for (int i = tin[to]; i <= tout[to]; ++i)
{
add(eul[i], to);
}
}
calc_col(v, v);
add(v, p);
ans[v] = mn;
if (!keep)
{
cnt[dep[v]] = 0;
for (int i = tin[v]; i <= tout[v]; ++i)
{
cnt[dep[eul[i]]] = 0;
}
for (int i = 0; i <= 30; ++i) mp[i] = inf;
}
}
void Erali_is_the_best()
{
cin >> n >> k;
sz[n] = 1;
for (int i = 0; i <= 30; ++i) mp[i] = inf;
for (int i = 1; i < n; ++i)
{
cin >> uu[i] >> vv[i];
uu[i] ++, vv[i] ++;
g[uu[i]].pb(vv[i]);
g[vv[i]].pb(uu[i]);
sz[i] = 1;
}
for (int i = 1, w; i < n; ++i)
{
cin >> w;
rib[{uu[i], vv[i]}] = w;
rib[{vv[i], uu[i]}] = w;
}
calc(1, 0);
dfs(1, 0, 0);
cout << (ans[1] == inf ? -1 : ans[1]) << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("stdin.in","r",stdin);
// freopen("stdin.out","w",stdout);
int tt = 1;
// cin >> tt;
for (int test = 1; test <= tt; ++test)
{
Erali_is_the_best();
}
}