ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214244 | #2763. 幻想乡的拜访 | erican | 0 | 2206ms | 112144kb | C++11 | 1.6kb | 2024-11-16 19:54:36 | 2024-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'