zoj 3516は木と関連しています

 
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4381
Conttest:ZOJ Monthly、July 2011
一本の木をあげます.10000個のノードで、各ノードには一つの権利があります.各ノードの権利値と父ノードを教えてください.その後、10000個のクエリをして、各ノードをルートとする子樹の最大3つの値を調べてください.もし3個の出力-1.
 
息子のノードを預けたくないので、各ノードの父ノードを預けて、それから毎回すべてのノードをスキャンして、葉っぱのノードを上に送ります.ちょっと注意してください.スキャンが多すぎるのを避けるために、上に送る過程で、あるノードの父ノードも息子ノードがない場合、直接にノードを上に送ります.(最後に非常に特殊なことを発見しました.やはり3*10^7になります.)
一番いい解法はやはりvectorで息子のノードを預けて、dfsを一つだけ預けたらいいです....一本の木に対してDFSはやりたい放題です.
 
コード:
 

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<memory.h>
using namespace std;

const int N=10010;
int m, n;
struct node
{
	int parent;
	int sonnum, cnt, a[3];
	void init()
	{
		sonnum = 0;
		cnt = 1;
	}
} a[N];

int cmp(int a, int b)
{
	return a>b;
}

void fun(int i)
{
	int l, k, j = a[i].parent;
	int b[6], bn;
	bn = 0;
	for(k=0; k<a[i].cnt; k++)
		b[bn++] = a[i].a[k];
	for(k=0; k<a[j].cnt; k++)
		b[bn++] = a[j].a[k];
	sort(b, b+bn, cmp);
	if(bn<=3)
		a[j].cnt = bn;
	else
		a[j].cnt = 3;
	for(k=0; k<a[j].cnt; k++)
		a[j].a[k] = b[k];
	a[j].sonnum--;
}

int main()
{
	int i, j, k, cas1=1, flag;
	while(scanf("%d", &n)!=EOF)
	{
		for(i=0; i<n; i++)
			a[i].init();
		scanf("%d", &a[0].a[0]);
		for(i=1; i<n; i++)
		{
			scanf("%d%d", &a[i].parent, &a[i].a[0]);
			j = a[i].parent;
			a[j].sonnum++;
		}
		flag = 1;
		while(flag)
		{
			for(i=1; i<n; i++)
			{
				j = i;
				while(j!=0 && a[j].sonnum==0 && a[j].parent!=-1)
				{
					flag = 0;
					fun(j);
					k = j;
					j = a[j].parent;
					a[k].parent = -1;
				}
			}
			if(flag==0)
				flag = 1;
			else
				break;
		}

		//printf("Case #%d:
", cas1++);
		scanf("%d", &m);
		while(m--)
		{
			scanf("%d", &i);
			if(a[i].cnt<3)
				printf("-1
");
			else
				printf("%d %d %d
", a[i].a[0], a[i].a[1], a[i].a[2]);
		}
	}

	return 0;
}