#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,a[200050],b[200050],st[200050][30],dp[200050],num[200050],ans;
vector<pair<int,int> >gr[200050];
void cal(int x,int p)
{
dp[x]=dp[p]+1;
st[x][0]=p;
for(int i=0;i<gr[x].size();i++)
{
int u=gr[x][i].first;
if(u==p)continue;
cal(u,x);
}
}
int lca(int x,int y)
{
if(dp[y]>dp[x])swap(x,y);
int dif=dp[x]-dp[y];
for(int i=0;i<23;i++)
{
if(dif&(1<<i))x=st[x][i];
}
if(x==y)return x;
for(int i=23;i>=0;i--)
{
if(st[x][i]!=st[y][i])
{
x=st[x][i];
y=st[y][i];
}
}
return st[x][0];
}
void dfs(int x,int p)
{
for(int i=0;i<gr[x].size();i++)
{
int u=gr[x][i].first;
if(u==p)continue;
dfs(u,x);
num[x]+=num[u];
}
}
void dfs1(int x,int p)
{
for(int i=0;i<gr[x].size();i++)
{
int u=gr[x][i].first,in=gr[x][i].second;
if(u==p)continue;
if(a[in]*num[u]<=b[in])ans+=a[in]*num[u];
else ans+=b[in];
dfs1(u,x);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n;
for(int i=0;i<n-1;i++)
{
int x,y;
cin>>x>>y>>a[i]>>b[i];
gr[x].push_back({y,i});
gr[y].push_back({x,i});
}
cal(1,0);
for(int i=1;i<=24;i++)
{
for(int j=1;j<=n;j++)st[j][i]=st[st[j][i-1]][i-1];
}
for(int i=1;i<n;i++)
{
int lc=lca(i,i+1);
if(lc==i)
{
num[i+1]++;
num[i]--;
}
else if(lc==i+1)
{
num[i]++;
num[i+1]--;
}
else
{
num[i]++;
num[i+1]++;
num[lc]-=2;
}
}
dfs(1,0);
dfs1(1,0);
cout<<ans;
}
Compilation message
putovanje.cpp: In function 'void cal(int, int)':
putovanje.cpp:10:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gr[x].size();i++)
~^~~~~~~~~~~~~
putovanje.cpp: In function 'void dfs(int, int)':
putovanje.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gr[x].size();i++)
~^~~~~~~~~~~~~
putovanje.cpp: In function 'void dfs1(int, int)':
putovanje.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gr[x].size();i++)
~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5112 KB |
Output is correct |
2 |
Correct |
9 ms |
5624 KB |
Output is correct |
3 |
Correct |
10 ms |
5752 KB |
Output is correct |
4 |
Correct |
10 ms |
5752 KB |
Output is correct |
5 |
Correct |
10 ms |
5752 KB |
Output is correct |
6 |
Correct |
8 ms |
5112 KB |
Output is correct |
7 |
Correct |
9 ms |
5240 KB |
Output is correct |
8 |
Correct |
9 ms |
5496 KB |
Output is correct |
9 |
Correct |
10 ms |
5624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
188 ms |
36344 KB |
Output is correct |
2 |
Correct |
187 ms |
37496 KB |
Output is correct |
3 |
Correct |
223 ms |
40988 KB |
Output is correct |
4 |
Correct |
236 ms |
41592 KB |
Output is correct |
5 |
Correct |
8 ms |
5244 KB |
Output is correct |
6 |
Correct |
192 ms |
35576 KB |
Output is correct |
7 |
Correct |
115 ms |
27000 KB |
Output is correct |
8 |
Correct |
199 ms |
36732 KB |
Output is correct |
9 |
Correct |
121 ms |
38520 KB |
Output is correct |
10 |
Correct |
117 ms |
37496 KB |
Output is correct |
11 |
Correct |
128 ms |
40440 KB |
Output is correct |
12 |
Correct |
135 ms |
40472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5112 KB |
Output is correct |
2 |
Correct |
9 ms |
5624 KB |
Output is correct |
3 |
Correct |
10 ms |
5752 KB |
Output is correct |
4 |
Correct |
10 ms |
5752 KB |
Output is correct |
5 |
Correct |
10 ms |
5752 KB |
Output is correct |
6 |
Correct |
8 ms |
5112 KB |
Output is correct |
7 |
Correct |
9 ms |
5240 KB |
Output is correct |
8 |
Correct |
9 ms |
5496 KB |
Output is correct |
9 |
Correct |
10 ms |
5624 KB |
Output is correct |
10 |
Correct |
188 ms |
36344 KB |
Output is correct |
11 |
Correct |
187 ms |
37496 KB |
Output is correct |
12 |
Correct |
223 ms |
40988 KB |
Output is correct |
13 |
Correct |
236 ms |
41592 KB |
Output is correct |
14 |
Correct |
8 ms |
5244 KB |
Output is correct |
15 |
Correct |
192 ms |
35576 KB |
Output is correct |
16 |
Correct |
115 ms |
27000 KB |
Output is correct |
17 |
Correct |
199 ms |
36732 KB |
Output is correct |
18 |
Correct |
121 ms |
38520 KB |
Output is correct |
19 |
Correct |
117 ms |
37496 KB |
Output is correct |
20 |
Correct |
128 ms |
40440 KB |
Output is correct |
21 |
Correct |
135 ms |
40472 KB |
Output is correct |
22 |
Correct |
170 ms |
36472 KB |
Output is correct |
23 |
Correct |
132 ms |
32632 KB |
Output is correct |
24 |
Correct |
163 ms |
35960 KB |
Output is correct |
25 |
Correct |
9 ms |
5368 KB |
Output is correct |
26 |
Correct |
60 ms |
19192 KB |
Output is correct |
27 |
Correct |
145 ms |
31480 KB |
Output is correct |
28 |
Correct |
105 ms |
34552 KB |
Output is correct |
29 |
Correct |
132 ms |
40440 KB |
Output is correct |
30 |
Correct |
126 ms |
40056 KB |
Output is correct |
31 |
Correct |
9 ms |
5496 KB |
Output is correct |