QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#604434 | #8758. Menji 和 gcd | xing4c# | RE | 0ms | 0kb | C++14 | 1.1kb | 2024-10-02 10:53:16 | 2024-10-02 10:53:17 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 2e5 + 7;
#define int long long
int n;
int w[N] = {0};
int fa[N] = {0};
vector<int> G[N];
int sum[N] = {0};
int siz[N] = {0};
int ans = 0;
bool cmp(int a, int b) {
return 1.0 * siz[a] / sum[a] > 1.0 * siz[b] / sum[b];
}
void dfs(int u = 1) {
for (auto to: G[u]) {
dfs(to);
sum[u] += sum[to];
siz[u] += siz[to];
}
}
int cnt = 0;
void dfs1(int u = 1) {
cnt++;
ans += cnt * w[u];
sort(G[u].begin(), G[u].end(), cmp);
for (auto to: G[u]) {
dfs1(to);
}
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
sum[i] = w[i];
siz[i] = 1;
}
for (int i = 2; i <= n; i++) {
cin >> fa[i];
G[fa[i]].push_back(i);
}
dfs();
dfs1();
cout << ans;
}
signed main() {
// freopen("D:\\Development_Software\\CLion\\CLionProjects\\Test\\in", "r", stdin);
ios::sync_with_stdio(false);
int T = 1;
while (T--)solve();
}
详细
Test #1:
score: 0
Runtime Error
input:
10 1 2 2 4 6 10 11 21 147 154 1470 1540 2890 3028 998244353 1000000007 34827364537 41029384775 147147147147 154154154154