2010-1103

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目类型： 

树、dfs 

题目大意： 

一棵树，每个结点有一个值，对任意一个结点可能有一个查询，如果以该结点为根的子树至少有3个结点，则输出最大的三个结点值，否则输出-1 

解题思路： 

从根节点开始，做一次dfs，每次更新子树的大小和最大的三个值。

代码： 


{{{
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <cstring>


using namespace std;

vector< vector<int> >a;
vector<int> b;
int x[10002][5];
int v[10002], p[10002];


void dfs(int c)
{
    int i, j, k, s;

    if (x[c][0]==-1)
    {
        x[c][0]=1;

        for (i=0; i<a[c].size(); i++)
        {
            s = a[c][i];
            dfs(s);
            x[c][0]+=x[s][0];
            for (j=1; j<=3; j++)
            {
                k=0;
                while (x[c][k+1]<x[s][j] && k<3)
                {
                    if (k!=0) x[c][k] = x[c][k+1];
                    k++;
                }
                if (x[c][k]<x[s][j] && k>0)
                    x[c][k] = x[s][j];
            }

        }

                k = 0;

                while (x[c][k+1]<v[c] && k<3)
                {
                    if (k!=0) x[c][k] = x[c][k+1];
                    k++;
                }
                if (x[c][k]<v[c] && k>0)
                    x[c][k] = v[c];


    }
}

int main()
{
    int i,j,k,m,n;

    b.clear();
    while (scanf("%d", &n)!=EOF)
    {
        a.clear();

        a.push_back(b);
        memset(x, -1, sizeof(x));


        scanf("%d", &v[0]);
        for (i=1; i<n; i++)
        {
            scanf("%d%d", &p[i], &v[i]);
            a.push_back(b);
        }
        for (i=1; i<n; i++)
        {
            k = p[i];
//          dad[i]=k;
            a[k].push_back(i);      
        }
        for (i=0; i<n; i++)
        {
            if (a[i].size()==0)
            {
                x[i][0]=1;
                x[i][3]=v[i];
            }

        }
        dfs(0);
        scanf("%d", &m);
        for (i=1; i<=m; i++)
        {
            scanf("%d", &j);
            if (x[j][0]<3)
            printf("-1\n");
            else
            {
                printf("%d %d %d\n", x[j][3], x[j][2], x[j][1]);

            }
        }

    }   




    return 0;
}

}}}


by sxstar

题目类型：

树、dfs

题目大意：

一棵树，每个结点有一个值，对任意一个结点可能有一个查询，如果以该结点为根的子树至少有3个结点，则输出最大的三个结点值，否则输出-1

解题思路：

从根节点开始，做一次dfs，每次更新子树的大小和最大的三个值。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <cstring>
using namespace std;
vector< vector<int> >a;
vector<int> b;
int x[10002][5];
int v[10002], p[10002];
void dfs(int c)
{
    int i, j, k, s;
    if (x[c][0]==-1)
    {
        x[c][0]=1;
        for (i=0; i<a[c].size(); i++)
        {
            s = a[c][i];
            dfs(s);
            x[c][0]+=x[s][0];
            for (j=1; j<=3; j++)
            {
                k=0;
                while (x[c][k+1]<x[s][j] && k<3)
                {
                    if (k!=0) x[c][k] = x[c][k+1];
                    k++;
                }
                if (x[c][k]<x[s][j] && k>0)
                    x[c][k] = x[s][j];
            }
        }
                k = 0;
                while (x[c][k+1]<v[c] && k<3)
                {
                    if (k!=0) x[c][k] = x[c][k+1];
                    k++;
                }
                if (x[c][k]<v[c] && k>0)
                    x[c][k] = v[c];
    }
}
int main()
{
    int i,j,k,m,n;
    b.clear();
    while (scanf("%d", &n)!=EOF)
    {
        a.clear();
        a.push_back(b);
        memset(x, -1, sizeof(x));
        scanf("%d", &v[0]);
        for (i=1; i<n; i++)
        {
            scanf("%d%d", &p[i], &v[i]);
            a.push_back(b);
        }
        for (i=1; i<n; i++)
        {
            k = p[i];
//          dad[i]=k;
            a[k].push_back(i);      
        }
        for (i=0; i<n; i++)
        {
            if (a[i].size()==0)
            {
                x[i][0]=1;
                x[i][3]=v[i];
            }
        }
        dfs(0);
        scanf("%d", &m);
        for (i=1; i<=m; i++)
        {
            scanf("%d", &j);
            if (x[j][0]<3)
            printf("-1\n");
            else
            {
                printf("%d %d %d\n", x[j][3], x[j][2], x[j][1]);
            }
        }
    }   
    return 0;
}

by sxstar