#include <bits/stdc++.h>
#define N 200005
#define pb push_back
#define sz(x) ll(x.size())
#define P 31
#define F first
#define S second
#define MOD ll(1000000007)
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
using namespace std;
typedef long long ll;
ll t[N + N + N][20], n, in[N], out[N], h[N], dp[N], ans;
vector <pair <pair <ll, ll>, ll> > g[N];
vector <ll> vr;
void dfs(ll v, ll p)
{
if (p != -1) h[v] = h[p] + 1;
in[v] = sz(vr);
vr.pb(v);
for (auto it : g[v])
{
if (it.S == p) continue;
dfs(it.S, v);
vr.pb(v);
}
out[v] = sz(vr);
vr.pb(v);
}
ll lca(ll x, ll y)
{
if (in[x] > in[y]) swap(x, y);
ll j = 0;
while ((1 << (j + 1)) <= in[y] - in[x] + 1) j++;
ll fr = t[in[x]][j];
ll sc = t[in[y] - (1 << j) + 1][j];
if (h[fr] > h[sc]) return sc;
return fr;
}
ll rec(ll v, ll p, ll c1, ll c2)
{
ll sm = 0;
for (auto it : g[v])
{
if (it.S == p) continue;
sm += rec(it.S, v, it.F.F, it.F.S);
}
sm += dp[v];
if (v != 1) ans += min(sm * c1, c2);
return sm;
}
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (ll i = 1; i < n; i++)
{
ll x, y, c1, c2;
cin >> x >> y >> c1 >> c2;
g[x].pb({{c1, c2}, y});
g[y].pb({{c1, c2}, x});
}
dfs(1, -1);
for (ll i = 0; i < sz(vr); i++) t[i][0] = vr[i];
for (ll j = 1; j < 20; j++)
for (ll i = 0; i < sz(vr); i++)
{
ll x = t[i][j - 1];
ll y = t[min(sz(vr) - 1, i + (1 << (j - 1)))][j - 1];
if (h[x] > h[y]) t[i][j] = y; else t[i][j] = x;
}
for (ll i = 1; i < n; i++)
{
ll lc = lca(i, i + 1);
dp[lc] -= 2;
dp[i]++; dp[i + 1]++;
}
rec(1, -1, -1, -1);
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
9 ms |
6144 KB |
Output is correct |
3 |
Correct |
9 ms |
6272 KB |
Output is correct |
4 |
Correct |
9 ms |
6400 KB |
Output is correct |
5 |
Correct |
9 ms |
6400 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5376 KB |
Output is correct |
8 |
Correct |
9 ms |
5888 KB |
Output is correct |
9 |
Correct |
9 ms |
6272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
62564 KB |
Output is correct |
2 |
Correct |
172 ms |
64352 KB |
Output is correct |
3 |
Correct |
200 ms |
70112 KB |
Output is correct |
4 |
Correct |
196 ms |
71516 KB |
Output is correct |
5 |
Correct |
10 ms |
5504 KB |
Output is correct |
6 |
Correct |
160 ms |
61288 KB |
Output is correct |
7 |
Correct |
113 ms |
45284 KB |
Output is correct |
8 |
Correct |
170 ms |
63328 KB |
Output is correct |
9 |
Correct |
151 ms |
67040 KB |
Output is correct |
10 |
Correct |
156 ms |
65120 KB |
Output is correct |
11 |
Correct |
166 ms |
70108 KB |
Output is correct |
12 |
Correct |
164 ms |
70364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
9 ms |
6144 KB |
Output is correct |
3 |
Correct |
9 ms |
6272 KB |
Output is correct |
4 |
Correct |
9 ms |
6400 KB |
Output is correct |
5 |
Correct |
9 ms |
6400 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
8 ms |
5376 KB |
Output is correct |
8 |
Correct |
9 ms |
5888 KB |
Output is correct |
9 |
Correct |
9 ms |
6272 KB |
Output is correct |
10 |
Correct |
165 ms |
62564 KB |
Output is correct |
11 |
Correct |
172 ms |
64352 KB |
Output is correct |
12 |
Correct |
200 ms |
70112 KB |
Output is correct |
13 |
Correct |
196 ms |
71516 KB |
Output is correct |
14 |
Correct |
10 ms |
5504 KB |
Output is correct |
15 |
Correct |
160 ms |
61288 KB |
Output is correct |
16 |
Correct |
113 ms |
45284 KB |
Output is correct |
17 |
Correct |
170 ms |
63328 KB |
Output is correct |
18 |
Correct |
151 ms |
67040 KB |
Output is correct |
19 |
Correct |
156 ms |
65120 KB |
Output is correct |
20 |
Correct |
166 ms |
70108 KB |
Output is correct |
21 |
Correct |
164 ms |
70364 KB |
Output is correct |
22 |
Correct |
198 ms |
64068 KB |
Output is correct |
23 |
Correct |
170 ms |
57192 KB |
Output is correct |
24 |
Correct |
190 ms |
63196 KB |
Output is correct |
25 |
Correct |
8 ms |
5760 KB |
Output is correct |
26 |
Correct |
82 ms |
32104 KB |
Output is correct |
27 |
Correct |
176 ms |
54888 KB |
Output is correct |
28 |
Correct |
131 ms |
60008 KB |
Output is correct |
29 |
Correct |
167 ms |
70364 KB |
Output is correct |
30 |
Correct |
159 ms |
69728 KB |
Output is correct |
31 |
Correct |
8 ms |
6016 KB |
Output is correct |