Tree of Three
Time Limit: 2 Seconds Memory Limit: 65536 KB
Now we have a tree and some queries to deal with. Every node in the tree has a value on it. For one node A, we want to know the largest three values in all the nodes of the subtree whose root is node A. Node 0 is root of the tree, except it, all other nodes have a parent node.
Input
There are several test cases. Each test case begins with a line contains one integer n(1 ≤ n ≤ 10000), which indicates the number of the node in the tree. The second line contains one integer v[0], the value on the root. Then for the following n - 1 lines(from the 3rd line to the (n + 1)th line), let i + 2 be the line number, then line i + 2contains two integers parent and v[i], here parent is node i's parent node, v[i] is the value on node i. Here 0 ≤ v[i] ≤ 1000000. Then the next line contains an integer m(1 ≤m ≤ 10000), which indicates the number of queries. Following m lines, each line contains one integer q, 0 ≤ q < n, it meas a query on node q.
Output
For each test case, output m lines, each line contains one or three integers. If the query asked for a node that has less than three nodes in the subtree, output a "-1"; otherwise, output the largest three values in the subtree, from larger to smaller.
Sample Input
5
1
0 10
0 5
2 7
2 8
5
0
1
2
3
4
Sample Output
10 8 7
-1
8 7 5
-1
-1
思路：深度优先搜索，一层一层由子节点向跟节点回溯。
1.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MAX 11111
using namespace std;
int Three_Max[MAX][], val[MAX], cnt[MAX];
typedef struct{
int to, next;
}Node;
Node edge[MAX];
int head[MAX];
void AddEdge(int u, int v, int i){
edge[i].to = v;
edge[i].next = head[u];
head[u] = i;
}
bool cmp(int a, int b){
return a > b;
}
void dfs(int id){
cnt[id] = ;
Three_Max[id][] = val[id];
for(int i = head[id];i != -;i = edge[i].next){
int u = edge[i].to;
dfs(u);
for(int j = ;j <= ;j ++) Three_Max[id][j] = Three_Max[u][j-];
sort(Three_Max[id] + , Three_Max[id]+, cmp);
cnt[id] += cnt[u];
}
}
int main(){
int n, m, cc, u, v, k;
while(~scanf("%d", &n)){
memset(head, -, sizeof(head));
memset(Three_Max, , sizeof(Three_Max));
memset(cnt, , sizeof(cnt));
k = ;
for(int i = ;i < n;i ++){
if( == i){
scanf("%d", &cc);
val[] = cc;
}else{
scanf("%d%d", &u, &cc);
val[i] = cc;
AddEdge(u, i, k);
k ++;
}
}
dfs();
scanf("%d", &m);
for(int i = ;i < m;i ++){
scanf("%d", &u);
if(cnt[u] < ) printf("-1\n");
else{
for(int j = ;j < ;j ++) printf("%d ", Three_Max[u][j]);
printf("%d\n", Three_Max[u][]);
}
}
}
return ;
}
2.
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MAX 11111
using namespace std;
int Three_Max[MAX][], val[MAX], cnt[MAX];
typedef struct{
int to, next;
}Node;
Node edge[MAX];
int head[MAX];
void AddEdge(int u, int v, int i){
edge[i].to = v;
edge[i].next = head[u];
head[u] = i;
}
bool cmp(int a, int b){
return a > b;
}
int *dfs(int id){
cnt[id] = ;
Three_Max[id][] = val[id];
for(int i = head[id];i != -;i = edge[i].next){
int u = edge[i].to;
int *temp = dfs(u);
for(int j = ;j <= ;j ++) Three_Max[id][j] = temp[j-];
sort(Three_Max[id] + , Three_Max[id]+, cmp);
cnt[id] += cnt[u];
}
return Three_Max[id];
}
int main(){
int n, m, cc, u, v, k;
while(~scanf("%d", &n)){
memset(head, -, sizeof(head));
memset(Three_Max, , sizeof(Three_Max));
memset(cnt, , sizeof(cnt));
k = ;
for(int i = ;i < n;i ++){
if( == i){
scanf("%d", &cc);
val[] = cc;
}else{
scanf("%d%d", &u, &cc);
val[i] = cc;
AddEdge(u, i, k);
k ++;
}
}
dfs();
scanf("%d", &m);
for(int i = ;i < m;i ++){
scanf("%d", &u);
if(cnt[u] < ) printf("-1\n");
else{
for(int j = ;j < ;j ++) printf("%d ", Three_Max[u][j]);
printf("%d\n", Three_Max[u][]);
}
}
}
return ;
}