UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214244#2763. 幻想乡的拜访erican02206ms112144kbC++111.6kb2024-11-16 19:54:362024-11-16 23:11:51

answer

// Problem: P3905 道路重建
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3905
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read(){
  int xx = 0, ff = 1;char ch = getchar();
  while (ch < '0' || ch > '9'){
    if (ch == '-')ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
	for (auto v: a) cerr << v << ' ';err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
	cerr << a << ' ';err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e6+5;
const ull P=137;
const int INF=1e18+7;
/*

策略


*/	



struct Node{
	int v,w;
};

vector<Node> e[N];

void add(int c,int b,int a){
	e[a].pb({b,c});
	e[b].pb({a,c});
}

int sz[N];
int n,ans;

int sum;

void dfs(int x,int fa){
	sz[x]=x;
	for(auto v:e[x]){
		if(v.v==fa)continue;
		dfs(v.v,x);
		sz[x]+=sz[v.v];
		ans+=(sz[v.v]*(sum-sz[v.v]))*v.w;
	}
}

signed main(){
	 n=rd;
	sum=(1+n)*n/2;
	for(int i=1;i<n;i++){
		add(1,rd,rd);
	}
	
	dfs(1,0);
	
	
	cout<<ans<<endl;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 0
Wrong Answer
time: 12ms
memory: 48100kb

input:

200
20 160
90 160
5 90
78 90
186 90
149 90
104 78
136 160
106 78
100 106
168 90
30 5
85 136
28 149
1...

output:

3104425912

result:

wrong answer 1st lines differ - expected: '104425891', found: '3104425912'

Test #2:

score: 0
Wrong Answer
time: 16ms
memory: 48100kb

input:

200
49 91
20 91
147 91
131 20
36 131
9 131
51 147
173 51
32 36
169 51
180 51
2 91
133 2
72 20
14 169...

output:

3145567238

result:

wrong answer 1st lines differ - expected: '145567217', found: '3145567238'

Test #3:

score: 0
Wrong Answer
time: 12ms
memory: 48096kb

input:

200
44 72
187 72
115 72
124 115
80 124
34 72
22 115
162 34
123 44
93 22
135 80
5 124
112 72
76 187
3...

output:

3226420673

result:

wrong answer 1st lines differ - expected: '226420652', found: '3226420673'

Test #4:

score: 0
Wrong Answer
time: 8ms
memory: 48276kb

input:

3000
940 1649
220 1649
1438 1649
2264 1649
1467 940
1825 220
1646 940
571 220
1419 220
2509 1438
264...

output:

1102392789313323

result:

wrong answer 1st lines differ - expected: '781596579', found: '1102392789313323'

Test #5:

score: 0
Wrong Answer
time: 8ms
memory: 48272kb

input:

3000
2156 216
2422 2156
2801 216
2504 2156
2701 2156
2582 2801
1558 2156
864 2582
737 864
2919 1558
...

output:

1187438244739725

result:

wrong answer 1st lines differ - expected: '236427659', found: '1187438244739725'

Test #6:

score: 0
Wrong Answer
time: 13ms
memory: 48272kb

input:

3000
2966 2885
2657 2885
2613 2966
1686 2613
2803 2885
191 2657
2824 2657
675 2657
2693 191
2798 191...

output:

1124119696089477

result:

wrong answer 1st lines differ - expected: '688220644', found: '1124119696089477'

Test #7:

score: 0
Wrong Answer
time: 682ms
memory: 112124kb

input:

1000000
984750 990109
970095 984750
996126 970095
998081 990109
987074 970095
962711 970095
916630 9...

output:

-4230816687312710397

result:

wrong answer 1st lines differ - expected: '192557796', found: '-4230816687312710397'

Test #8:

score: 0
Wrong Answer
time: 557ms
memory: 111980kb

input:

1000000
947305 936749
948062 947305
970449 947305
988744 948062
998703 988744
986194 947305
997762 9...

output:

-4464452851023646162

result:

wrong answer 1st lines differ - expected: '160385007', found: '-4464452851023646162'

Test #9:

score: 0
Wrong Answer
time: 451ms
memory: 112144kb

input:

1000000
952012 962256
982471 962256
955412 952012
953636 962256
991390 952012
998704 953636
999294 9...

output:

-1566276884669722587

result:

wrong answer 1st lines differ - expected: '308556344', found: '-1566276884669722587'

Test #10:

score: 0
Wrong Answer
time: 447ms
memory: 112108kb

input:

1000000
900864 972452
986047 900864
953966 972452
977801 986047
997024 972452
954755 953966
999240 9...

output:

-4183302940864130558

result:

wrong answer 1st lines differ - expected: '201471911', found: '-4183302940864130558'