#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200001;
ll bit1[200001],bit2[200001];
unsigned int s[maxn],d_hld[maxn],cl[maxn],pos[maxn],id=0,head[maxn],pd[maxn],n,e_pre[maxn];
struct item
{
int v,t1,t2;
};
vector<item>g[maxn];
void dfs(int u)
{
cl[u]=1;
s[u]=1;
int smax=0,imax=0;
for (int i=0;i<g[u].size();i++){
int v=g[u][i].v;
if (cl[v]==0){
pd[v]=u;
dfs(v);
s[u]+=s[v];
if (smax<s[v]){
smax=s[v];
imax=i;
}
}
}
swap(g[u][0],g[u][imax]);
}
void hld(int u)
{
pos[u]=++id;
for (item &i:g[u]){
int v=i.v;
if (pd[v]==u){
if (2*s[v]>=s[u]) head[v]=head[u],d_hld[v]=d_hld[u];
else head[v]=v,d_hld[v]=d_hld[u]+1;
hld(v);
}
}
}
void update1(int i,ll v)
{
while (i<=n){
bit1[i]+=v;
i+=(i&-i);
}
}
void update2(int i,ll v)
{
while (i<=n){
bit2[i]+=v;
i+=(i&-i);
}
}
ll query1(int i)
{
ll ans=0;
while (i>0){
ans+=bit1[i];
i&=(i-1);
}
return ans;
}
ll query2(int i)
{
ll ans=0;
while (i>0){
ans+=bit2[i];
i&=(i-1);
}
return ans;
}
void updaterange(int l,int r,int v)
{
update1(l,(n-l+1)*v);
update1(r+1,-(n-r)*v);
update2(l,v);
update2(r+1,-v);
}
ll prefixsum(int i)
{
return (ll)query1(i)-query2(i)*(n-i);
}
ll rangesum(int l,int r)
{
return prefixsum(r)-prefixsum(l-1);
}
void mov(int u,int v)
{
while (d_hld[u]>d_hld[v]){
//cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
updaterange(pos[head[u]]+1,pos[u],1);
u=head[u];
e_pre[u]++;
u=pd[u];
}
while (d_hld[v]>d_hld[u]){
// cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
updaterange(pos[head[v]]+1,pos[v],1);
v=head[v];
e_pre[v]++;
v=pd[v];
}
while (head[u]!=head[v]){
// cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
updaterange(pos[head[u]]+1,pos[u],1);
u=head[u];
e_pre[u]++;
u=pd[u];
updaterange(pos[head[v]]+1,pos[v],1);
v=head[v];
e_pre[v]++;
v=pd[v];
}
if (pos[u]<pos[v])
updaterange(pos[u]+1,pos[v],1);
else
updaterange(pos[v]+1,pos[u],1);
}
unsigned int query(int u,int v)
{
unsigned int kq=0;
while (d_hld[u]>d_hld[v]){
// cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
kq+=rangesum(pos[head[u]]+1,pos[u]);
u=head[u];
kq+=e_pre[u];
u=pd[u];
}
while (d_hld[u]<d_hld[v]){
// cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
kq+=rangesum(pos[head[v]]+1,pos[v]);
v=head[v];
kq+=e_pre[v];
v=pd[v];
}
while (head[u]!=head[v]){
// cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
kq+=rangesum(pos[head[u]]+1,pos[u]);
u=head[u];
kq+=e_pre[u];
u=pd[u];
kq+=rangesum(pos[head[v]]+1,pos[v]);
v=head[v];
kq+=e_pre[v];
v=pd[v];
}
if (pos[u]<pos[v])
kq+=rangesum(pos[u]+1,pos[v]);
else
kq+=rangesum(pos[v]+1,pos[u]);
return kq;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
int a,b,c,d;
for (int i=1;i<n;i++){
cin>>a>>b>>c>>d;
g[a].push_back({b,c,d});
g[b].push_back({a,c,d});
}
dfs(1);
hld(1);
//cout<<1<<endl;
for (int i=1;i<n;i++)
mov(i,i+1);
//cout<<1<<endl;
long long s=0;
for (int i=1;i<=n;i++){
for (item j:g[i]){
s+=min((long long )query(i,j.v)*j.t1, (long long)j.t2);
}
}
cout<<(long long)s/2;
}
Compilation message
putovanje.cpp: In function 'void dfs(int)':
putovanje.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i=0;i<g[u].size();i++){
| ~^~~~~~~~~~~~
putovanje.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
23 | if (smax<s[v]){
| ~~~~^~~~~
putovanje.cpp: In function 'void hld(int)':
putovanje.cpp:36:18: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
36 | if (pd[v]==u){
| ~~~~~^~~
putovanje.cpp: In function 'void update1(int, long long int)':
putovanje.cpp:45:13: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
45 | while (i<=n){
| ~^~~
putovanje.cpp: In function 'void update2(int, long long int)':
putovanje.cpp:52:13: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
52 | while (i<=n){
| ~^~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
166 | for (int i=1;i<n;i++){
| ~^~
putovanje.cpp:174:19: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
174 | for (int i=1;i<n;i++)
| ~^~
putovanje.cpp:178:19: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
178 | for (int i=1;i<=n;i++){
| ~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12892 KB |
Output is correct |
2 |
Correct |
4 ms |
12892 KB |
Output is correct |
3 |
Correct |
4 ms |
13008 KB |
Output is correct |
4 |
Correct |
4 ms |
13016 KB |
Output is correct |
5 |
Correct |
4 ms |
13032 KB |
Output is correct |
6 |
Correct |
3 ms |
12944 KB |
Output is correct |
7 |
Correct |
2 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
4 ms |
13020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
21656 KB |
Output is correct |
2 |
Correct |
53 ms |
23032 KB |
Output is correct |
3 |
Correct |
76 ms |
24544 KB |
Output is correct |
4 |
Correct |
62 ms |
23788 KB |
Output is correct |
5 |
Correct |
3 ms |
12888 KB |
Output is correct |
6 |
Correct |
70 ms |
21548 KB |
Output is correct |
7 |
Correct |
40 ms |
19524 KB |
Output is correct |
8 |
Correct |
66 ms |
21692 KB |
Output is correct |
9 |
Correct |
55 ms |
21736 KB |
Output is correct |
10 |
Correct |
63 ms |
21584 KB |
Output is correct |
11 |
Correct |
59 ms |
22352 KB |
Output is correct |
12 |
Correct |
72 ms |
22480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12892 KB |
Output is correct |
2 |
Correct |
4 ms |
12892 KB |
Output is correct |
3 |
Correct |
4 ms |
13008 KB |
Output is correct |
4 |
Correct |
4 ms |
13016 KB |
Output is correct |
5 |
Correct |
4 ms |
13032 KB |
Output is correct |
6 |
Correct |
3 ms |
12944 KB |
Output is correct |
7 |
Correct |
2 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
4 ms |
13020 KB |
Output is correct |
10 |
Correct |
55 ms |
21656 KB |
Output is correct |
11 |
Correct |
53 ms |
23032 KB |
Output is correct |
12 |
Correct |
76 ms |
24544 KB |
Output is correct |
13 |
Correct |
62 ms |
23788 KB |
Output is correct |
14 |
Correct |
3 ms |
12888 KB |
Output is correct |
15 |
Correct |
70 ms |
21548 KB |
Output is correct |
16 |
Correct |
40 ms |
19524 KB |
Output is correct |
17 |
Correct |
66 ms |
21692 KB |
Output is correct |
18 |
Correct |
55 ms |
21736 KB |
Output is correct |
19 |
Correct |
63 ms |
21584 KB |
Output is correct |
20 |
Correct |
59 ms |
22352 KB |
Output is correct |
21 |
Correct |
72 ms |
22480 KB |
Output is correct |
22 |
Correct |
134 ms |
19164 KB |
Output is correct |
23 |
Correct |
116 ms |
18252 KB |
Output is correct |
24 |
Correct |
134 ms |
18916 KB |
Output is correct |
25 |
Correct |
3 ms |
13008 KB |
Output is correct |
26 |
Correct |
51 ms |
15420 KB |
Output is correct |
27 |
Correct |
100 ms |
18044 KB |
Output is correct |
28 |
Correct |
44 ms |
20308 KB |
Output is correct |
29 |
Correct |
65 ms |
22500 KB |
Output is correct |
30 |
Correct |
57 ms |
22188 KB |
Output is correct |
31 |
Correct |
3 ms |
13000 KB |
Output is correct |