Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 4068K 235MS 1A 要写静態树不然可能T（没试过）

Posted by KatrineYang at 2016-09-16 14:34:32 on Problem 1339
```#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;

struct node{
node *left, *right;
int weight;
} pool[200002];

struct push_node{
int bh;
int weight;
};

bool operator<(const node &n1, const node &n2){
return n1.weight > n2.weight;
}

bool operator<(const push_node &pn1, const push_node &pn2){
return pn1.weight > pn2.weight;
}

int getSum(node *root, int depth){
if(root->left){
return getSum(root->left, depth+1) + getSum(root->right, depth+1);
}
return root->weight * depth;
}

int main() {
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ii++){
int n;
scanf("%d", &n);
int poolCnt = 0;
priority_queue<push_node> pq;
for(int i = 0; i < n; i++){
int temp;
scanf("%d", &temp);
pool[poolCnt].weight = temp;
pool[poolCnt].left = NULL;
pool[poolCnt].right = NULL;
push_node pn;
pn.bh = poolCnt;
pn.weight = temp;
pq.push(pn);
poolCnt++;
}
node *root;
for(int i = 0; i < n-1; i++){
push_node pn1 = pq.top();
pq.pop();
push_node pn2 = pq.top();
pq.pop();
pool[poolCnt].weight = pn1.weight + pn2.weight;
pool[poolCnt].left = &pool[pn1.bh];
pool[poolCnt].right = &pool[pn2.bh];
if(i == n-2){
root = &pool[poolCnt];
}
else{
push_node pn;
pn.bh = poolCnt;
pn.weight = pool[poolCnt].weight;
pq.push(pn);
}
poolCnt++;
}
printf("%d\n", getSum(root, 0));
}
return 0;
}
```

Followed by: