#include<bits/stdc++.h>
//#include "traffic.h"
/*
7
10 20 10 10
20 30 40
0 1
0 2
0 3
3 6
2 5
1 4
*/
using namespace std;
vector<vector<int>>g;
vector<long long>fans;
vector<long long>sub, res;
void calc(int node, int par){
sub[node] = fans[node];
for(int v : g[node]){
if(v != par){
calc(v, node);
sub[node] += sub[v];
}
}
}
void traverse(int node, int par){
res[node] = max(res[node], sub[0] - sub[node]);
for(int v : g[node]){
if(v == par)continue;
res[node] = max(sub[v], res[node]);
}
for(int v : g[node]){
if(v != par){
traverse(v, node);
}
}
}
int LocateCentre(int n, int p[], int s[], int d[]){
g.resize(n);
fans.resize(n);
res.resize(n);
sub.resize(n);
for(int i = 0;i < n - 1;++i){
g[s[i]].push_back(d[i]);
g[d[i]].push_back(s[i]);
}
for(int i = 0;i < n;++i){
fans[i] = p[i];
}
calc(1, 1);
traverse(1, 1);
long long mn = 1e18, id = -1;
for(int i = 0;i < n;++i){
if(mn > res[i]){
mn = res[i];
id = i;
}
}
return id;
}
//int main()
//{
// int n;
// cin >> n;
// g.resize(n);
// fans.resize(n);
// res.resize(n);
// sub.resize(n);
// for(int i = 0;i < n;++i){
// cin >> fans[i];
// }
// for(int i = 0;i < n - 1;++i){
// int u, v;
// cin >> u >> v;
// g[u].push_back(v);
// g[v].push_back(u);
// }
//
// calc(0, 0);
// traverse(0, 0);
// int mn = 1e9, id = -1;
// for(int i = 0;i < n;++i){
// if(mn > res[i]){
// mn = res[i];
// id = i;
// }
// cout << i << ": " << res[i] << ", " << sub[i] << '\n';
// }
// cout << id;
//}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |